LeetCode-226. 翻转二叉树

叁歲伎倆 2024-03-27 15:36 102阅读 0赞

#### 目录 ####

*   *  题目分析
     *  前序遍历
     *  中序遍历
     *  后序遍历

题目来源  
[226. 翻转二叉树][226.]

### 题目分析 ###

如果要从整个树来看，翻转还真的挺复杂，整个树以中间分割线进行翻转，如图：  
![在这里插入图片描述][19d637e45b0c48f091d64e6f7ae231ac.png]  
可以发现想要翻转它，其实就把每一个节点的左右孩子交换一下就可以了。  
**注意只要把每一个节点的左右孩子翻转一下，就可以达到整体翻转的效果**  
**这道题目使用前序遍历和后序遍历都可以，唯独中序遍历不方便，因为中序遍历会把某些节点的左右孩子翻转了两次！**

### 前序遍历 ###

**递归三部曲：**

*  确定递归函数的参数和返回值  
    返回值的话其实也不需要，但是题目中给出的要返回root节点的指针，可以直接使用题目定义好的函数，

TreeNode invertTree(TreeNode root)

*  确定终止条件  
    当前节点为空的时候，就返回

if(root == null){
        
                return root;
            }

*  确定单层递归的逻辑  
    因为是先前序遍历，所以先进行交换左右孩子节点，然后反转左子树，反转右子树。

TreeNode temp = root.left;
            root.left = root.right;
            root.right = temp;
            invertTree(root.left);
            invertTree(root.right);

![在这里插入图片描述][00c707b461744589a3519e14b372d574.gif_pic_center]  
基于这递归三步法，代码基本写完  
**第一种方式**

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

**第二种方式**  
定义一个swap方法

class Solution {
        
        public TreeNode invertTree(TreeNode root) {
        
            if(root == null){
        
                return root;
            }
            swap(root);
            invertTree(root.left);
            invertTree(root.right);
            return root;
        }
    
        public static void swap(TreeNode root){
        
            TreeNode temp = root.left;
            root.left = root.right;
            root.right = temp;
        }
    }

![在这里插入图片描述][cd932acaf9e5471a90eaedc3b93a53c3.png]

### 中序遍历 ###

中序遍历为啥不行，发现右边处理好了，而左边没有旋转好，我们只需要最后旋转左边就行了  
![在这里插入图片描述][f1b1c61416e844c98bd15f7ef05ce946.png]

class Solution {
        
        public TreeNode invertTree(TreeNode root) {
        
            if(root == null){
        
                return root;
            }
            invertTree(root.left);
            swap(root);
            invertTree(root.left);
            return root;
        }
    
        public static void swap(TreeNode root){
        
            TreeNode temp = root.left;
            root.left = root.right;
            root.right = temp;
        }
    }

![在这里插入图片描述][2c4bb21d80c44af5922af78cd164d5fd.png]

### 后序遍历 ###

和前序遍历一样，但后续遍历是从下而上

class Solution {
        
        public TreeNode invertTree(TreeNode root) {
        
            if(root == null){
        
                return root;
            }
            invertTree(root.left);
            invertTree(root.right);
            swap(root);
            return root;
        }
    
        public static void swap(TreeNode root){
        
            TreeNode temp = root.left;
            root.left = root.right;
            root.right = temp;
        }
    }

![在这里插入图片描述][c956a5b5058c4eff84a9b224aa569e0b.png]

[226.]: https://leetcode.cn/problems/invert-binary-tree/
[19d637e45b0c48f091d64e6f7ae231ac.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/b56d73f472904fa58fbbba529b78cdee.png
[00c707b461744589a3519e14b372d574.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/4f50852352a34a1196cee57a326d6c79.png
[cd932acaf9e5471a90eaedc3b93a53c3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/28d4362b23f647d2b46edcd29782a432.png
[f1b1c61416e844c98bd15f7ef05ce946.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/ea39c2071c9d4ed0875eea9fd8d4a827.png
[2c4bb21d80c44af5922af78cd164d5fd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/734d6aec79f3451882ef361c50243078.png
[c956a5b5058c4eff84a9b224aa569e0b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/aa4e488b715f46f085a10627a9cd740b.png