By

前言

Github：https://github.com/HealerJean

博客：http://blog.healerjean.com

1、翻转二叉树

翻转一棵二叉树。

示例：

输入：

	  4
    /   \
  2      7
 / \    / \
1   3  6   9

输出：

     4
   /   \
  7     2
 / \   / \
9   6 3   1

1.1、解题思路

基本上很简单，就是遍历一棵树而已

1.2、算法

1.2.1、算法1

/**
* 1、我的解法 （从前往后）
 */
public TreeNode invertTree(TreeNode root) {
    if (root == null){
        return null;
    }
    //左右节点交换
    TreeNode temp = root.left ;
    root.left = root.right;
    root.right = temp;

    invertTree(root.left);
    invertTree(root.right);

    return root;
}

1.2.1、算法2

/**
* 2、官方解法（从后往前）
*/
public TreeNode invertTree2(TreeNode root) {
    if (root == null) {
        return null;
    }
    TreeNode left = invertTree2(root.left);
    TreeNode right = invertTree2(root.right);

    root.left = right;
    root.right = left;
    return root;
}

1.3、测试

@Test
public void test(){
    System.out.println(invertTree(initTreeNode()));
}


public TreeNode initTreeNode(){
    TreeNode treeNode6 = new TreeNode(6, null, null);
    TreeNode treeNode9 = new TreeNode(9, null, null);
    TreeNode treeNode7 = new TreeNode(7, treeNode6, treeNode9);


    TreeNode treeNode3 = new TreeNode(3, null, null);
    TreeNode treeNode1 = new TreeNode(1, null ,null);
    TreeNode treeNode2 = new TreeNode(2, treeNode1 , treeNode3);
    TreeNode root4 = new TreeNode(4, treeNode2, treeNode7);
    return root4 ;
}

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
    TreeNode(int x, TreeNode left, TreeNode right) {
        this.val = x;
        this.left = left;
        this.right = right;

    }
}

​

ContactAuthor