翻转二叉树

爱被打了一巴掌 2022-12-08 12:57 137阅读 0赞

# 翻转二叉树 #

## 1、参考资料 ##

https://leetcode-cn.com/problems/invert-binary-tree/

## 2、题目要求 ##

> 题目要求

翻转一棵二叉树。

> 示例：

输入：

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

输出：

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

> 备注:

这个问题是受到 [Max Howell ][Max Howell]的 [原问题][Link 1] 启发的 ：

谷歌：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。

## 3、代码思路 ##

递归

1.  额，怎么说呢？一般遇到二叉树的问题，首先都会想到深度优先遍历，那么递归自然就少不了
2.  假设我们从根节点 `root` 开始进行递归，其实就是将 `root` 的左右子树互相调换一下，但此时 `root` 的左子树，右子树并没有翻转，那么我们再将 `root.left` 进行翻转，将 `root.right` 进行翻转。。。以此类推
3.  但是对于二叉树而言，我们只能先递归到最深层，翻转最深层的子树，然后再依次回溯翻转上层的子树
4.  我们定义 `TreeNode invertTree(TreeNode root) {` 函数用于翻转根节点为 `root` 的子树，返回值为翻转后的根节点
5.  二话不说，回溯条件肯定是 `if (root == null) {`，此时应该 `return null`，因为该子树的根节点为 `null`
6.  接下来就是编写递归翻转的具体逻辑了，从上面的分析可知，我们需要分别翻转 `root` 的左右子树，翻转左子树：`TreeNode left = invertTree(root.left);`；翻转右子树：`TreeNode right = invertTree(root.right);`
7.  执行完翻转左子树的操作后，左子树应该和右子树对调，即 `root.left = right; root.right = left;`，最后，我们返回根节点 `root` 即可

--------------------

举例想想具体的执行逻辑

1.  二叉树如下
    
        4
           /   \
          7     2
         / \   / \
        9   6 3   1
2.  当递归执行到节点 `7` 时，此时 `root == 7`，即当前正在执行根节点为 `7` 的子树的翻转，会执行如下语句：`TreeNode left = invertTree(root.left); TreeNode right = invertTree(root.right);`
3.  先执行左递归 `TreeNode left = invertTree(root.left);` 至节点 `9`(翻转节点 `7` 的左节点)，此时同样会执行根节点为 `9` 的子树的翻转：`TreeNode left = invertTree(root.left); TreeNode right = invertTree(root.right);`，恰好节点 `9` 没有左右子树，执行递归时会 `return null`
4.  当执行完节点 `9` 的递归之后，会执行右递归 `TreeNode right = invertTree(root.right);` 至节点 `6`(翻转节点 `7` 的右节点)，同样节点 `6` 没有左右子树，执行递归翻转时会 `return null`
5.  执行完如上步骤后，`left` 为节点 `9`，`right` 为节点 `6`，此时需要执行根节点为 `7` 的子树的翻转，执行完翻转之后，即 `root.left = right; root.right = left;`(左变右，右变左)，然后 `return 根节点7` 进行回溯
6.  以此类推。。。

## 4、代码实现 ##

代码

/**
     * @ClassName InvertTreeDemo
     * @Description TODO
     * @Author Heygo
     * @Date 2020/9/19 10:44
     * @Version 1.0
     */
    public class InvertTreeDemo {
        
    
        class Solution {
        
    
            /**
             * 翻转根节点为 root 的子树
             *
             * @param root 待翻转二叉树的根节点
             * @return 翻转后二叉树的根节点
             */
            public TreeNode invertTree(TreeNode root) {
        
                // 该子树的根节点为 null，所以 return null;
                if (root == null) {
        
                    return null;
                }
                // 翻转 root 的左子树
                TreeNode left = invertTree(root.left);
                // // 翻转 root 的右子树
                TreeNode right = invertTree(root.right);
                // 左变右，右变左，完成翻转
                root.left = right;
                root.right = left;
                // 返回子树的根节点
                return root;
            }
        }
    
        public class TreeNode {
        
            int val;
            TreeNode left;
            TreeNode right;
    
            TreeNode(int x) {
        
                val = x;
            }
        }
    
    }

[Max Howell]: https://twitter.com/mxcl
[Link 1]: https://twitter.com/mxcl/status/608682016205344768