翻转二叉树(深搜-先序遍历-交换Node)

题目：翻转二叉树，例如

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

to

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

已知二叉树的节点定义如下：

class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode(int x) { val = x; }
}

分析：该题有个小故事：Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.

该题可以使用深搜中的先序遍历的思路，依次交换左右TreeNode，注意是交换TreeNode，而不是交换TreeNode的值。下面是翻转的过程：

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

AC代码如下：

    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

优质内容筛选与推荐>>
1、190906mysql常用语法
2、跟着大彬读源码 - Redis 6 - 对象和数据类型（下）
3、下一代无服务器的发展形态： Serverless2.0
4、2018-2019-2 网络对抗技术 20165308 Exp3 免杀原理与实践
5、openstack 基镜像展开过程

0 │ 收藏 │ 举报

朋友将在看一看看到

分享想法到看一看