leetcode226.翻转二叉树(二叉树的前序遍历)

leetcode226.翻转二叉树(二叉树的前序遍历)

二月 23, 2020

leetcode226. 翻转二叉树

翻转一棵二叉树。

示例：
输入：
  4
/   \
2    7
/ \   / \
1 3 6 9
输出：
 4
/  \
7   2
/ \   / \
9 6 3 1
备注:
这个问题是受到 Max Howell 的 原问题 启发的 ：
谷歌：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了.

(我查看原来的推特下面还有一个评论，大概意思就是：做好你四年的算法作业，比你实际做出来任何东西都要好。)

思路

二叉树的前序遍历，用把每次遍历的子树返回给一个新的节点，再用这些节点创造一个二叉树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public TreeNode invertTree(TreeNode root) {
        TreeNode node=new TreeNode(-1);
        node=root;
        if(node!=null){
        //这里一定要先赋值在进行之后的操作
            TreeNode l=root.left;
            TreeNode r=root.right;
            //如果这里写node.right=invertTree(root.left);
                //node.left=invertTree(root.right);走上面的语句没问题，但是走到这一行的时候，会发现root.right已经有值了（上面一行赋的值），
                //所以得先把两个子树存起来
                node.right=invertTree(l);
                node.left=invertTree(r);
        }
        return node;
    }

leetcode 24/100