Invert a binary tree 두 갈래 나무 뒤집기

2989 단어
Invert a binary tree 두 갈래 나무 뒤집기
다음과 같은 두 갈래 나무가 있다고 가정합니다: 4/\2 7/\/\1 3 6 9 뒤집기:
       4     /   \    7     2   /\   /\  9  6  3  1
이곳은 귀속적인 방법을 채택하여 처리한다.결점을 두루 돌아다니며 각 결점의 두 개의 하위 결점을 위치를 교환하면 된다.왼쪽 나무부터 층층이 깊이 들어가 밑에서 위로 결점의 좌우 결점을 처리한다.그리고 오른쪽 나무를 처리하세요.
모든 코드는 다음과 같습니다.
public class InvertBinaryTree {

    public static void main(String args[]) {
        TreeNode root = new TreeNode(0); //  
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        root.left = node1;
        root.right = node2;
        node1.left = node3;
        node1.right = node4;
        node2.left = node5;
        node2.right = node6;
        node4.right = node7;

        preOrderTravels(root);          //  
        System.out.println();
        root = invertBinaryTree(root);
        preOrderTravels(root);          //  

    }
    //  
    public static void preOrderTravels(TreeNode node) {
        if (node == null) {
            return;
        } else {
            System.out.print(node.val + " ");
            preOrderTravels(node.left);
            preOrderTravels(node.right);
        }
    }
    //  
    private static TreeNode invertBinaryTree(TreeNode root) {
        if (root == null|| (root.left == null && root.right == null))
            return root;//  , , 
        TreeNode tmp = root.right;               //  tmp 
        root.right = invertBinaryTree(root.left);//  , root 
        root.left = invertBinaryTree(tmp);       //  tmp , root 
        return root;
    }
}

 
출력: 0 1 3 4 7 2 5 6 5 1 4 7 3

좋은 웹페이지 즐겨찾기