이 진 트 리 반전 의 재 귀 와 비 재 귀 실현 (자바)

2018 단어 데이터 구조
두 갈래 나무의 뒤 집기, 즉 뿌리 가 있 는 수직선 을 대칭 선 으로 하고 대칭 위치의 두 노드 를 교환한다.
이런 알고리즘 을 실현 하면 재 귀 와 비 재 귀 (스 택) 두 가지 사고 가 있 을 수 있다.
다음은 자바 코드 구현.
import java.util.Stack;

/**
 * Created by Lee on 2017/11/11.
 */
//   
class Node {
    int value;
    Node left;
    Node right;

    Node(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                ", left=" + left +
                ", right=" + right +
                '}';
    }
}
public class InvertBinaryTreeDemo {

    public static void swap(Node root){
        Node temp = root.left;
        root.left = root.right;
        root.right = temp;
    }

    //    
    public static Node invert(Node root){
        if (root == null){
            return null;
        }
        root.left = invert(root.left);
        root.right = invert(root.right);
        swap(root);
        return root;
    }

    //   ,    
    public static void invertByStack(Node root){
        Stack stack = new Stack();
        stack.push(root);
        while (!stack.empty()){
            Node node = stack.pop();
            swap(node);
            if (node.left != null){
                stack.push(node.left);
            }
            if (node.right != null){
                stack.push(node.right);
            }
        }
    }

    //  
    public static void main(String[] args) {
        Node node0 = new Node(1);
        Node node1 = new Node(2);
        Node node2 = new Node(3);
        Node node3 = new Node(4);
        Node node4 = new Node(5);
        Node node5 = new Node(6);
        Node node6 = new Node(7);
        node0.left = node1;
        node0.right = node2;
        node1.left = node3;
        node1.right = node4;
        node2.left = node5;
        node2.right = node6;
        //invertByStack(node0);
        //invert(node0);
        System.out.println(node0);
    }
}

좋은 웹페이지 즐겨찾기