226. 翻转二叉树

缺乏、安全感 2023-10-15 19:51 46阅读 0赞

### 226. 翻转二叉树 ###

*  题干描述
 *  解题原理
 *  递归法
 *   *  1. 确定递归函数的参数和返回值
     *  2. 确定终止条件
     *  3. 确定单层递归的逻辑
 *  迭代法
 *   *  1. 深度优先遍历
     *  2. 广度优先遍历
 *  拓展
 *  具体代码
 *   *  1. DFS递归
     *  2. BFS

# 题干描述 #

[力扣入口-226.翻转二叉树][-226.]

翻转一棵二叉树。

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

# 解题原理 #

想要实现翻转，其实就是把每一个节点的左右孩子交换一下。

注意只要把每一个节点的左右孩子翻转一下，就可以达到整体翻转的效果。

**这道题目使用前序遍历和后序遍历都可以，唯独中序遍历不方便，因为中序遍历会把某些节点的左右孩子翻转了两次！建议拿纸画一画，就理解了。**

也可以采用层序遍历。

# 递归法 #

## 1. 确定递归函数的参数和返回值 ##

参数就是要传入节点的指针，不需要其他参数了，通常此时定下来主要参数，如果在写递归的逻辑中发现还需要其他参数的时候，随时补充。

返回值的话其实也不需要，但是题目中给出的要返回root节点的指针，可以直接使用题目定义好的函数，所以函数的返回类型为`TreeNode* invertTree(TreeNode* root)`。

## 2. 确定终止条件 ##

当前节点为空的时候，就返回

if(root == NULL) return root;

## 3. 确定单层递归的逻辑 ##

因为是先前序遍历，所以先进行交换左右孩子节点，然后反转左子树，反转右子树。

swap(root->left, root->right);
    invertTree(root->left);
    invertTree(root->right);

基于这递归三步法，代码基本写完，C++代码如下：

class Solution{
        
    public:
    	TreeNode* invertTree(TreeNode* root){
        
    		if(root == NULL) return root;
    		swap(root->left, root->right); // 中
    		invertTree(root->left); // 左
    		invertTree(root->right); // 右
    		return root;
    	}
    };

# 迭代法 #

## 1. 深度优先遍历 ##

递归能做的，栈也能做。

## 2. 广度优先遍历 ##

也就是层序遍历，层序遍历也是可以翻转这棵树的，因为层序遍历也可以把每个节点的左右孩子都翻转一遍。

# 拓展 #

**已经指出递归的中序遍历是不行的，因为使用递归的中序遍历，某些节点的左右孩子会翻转两次。**

但使用迭代方式统一写法的中序是可以的。该中序可以的原因子在于，这是用栈来遍历，而不是靠指针来遍历，避免了递归法中翻转了两次的情况。

# 具体代码 #

## 1. DFS递归 ##

// 226.翻转二叉树 - DFS递归
    /**
     * 前后序遍历都可以
     * 中序可以，因为先左孩子交换孩子，再根交换孩子（做完后，右孩子已经变成了原来的左孩子），再右孩子交换孩子（此时其实是对原来的左孩子做交换）
     */
    public TreeNode invertTree(TreeNode root){
        
        if(root == null){
        
            return null;
        }
        invertTree(root.left);
        invertTree(root.right);
        swapChildren(root);
        return root;
    }
    
    private void swapChildren(TreeNode root){
        
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
    }

## 2. BFS ##

// 226.翻转二叉树 - BFS
    public TreeNode invertTree2(TreeNode root){
        
        if(root == null) {
        return null;}
        ArrayDeque<TreeNode> deque = new ArrayDeque<>();
        deque.offer(root);
        while(!deque.isEmpty()){
        
            int size = deque.size();
            while(size-- > 0){
        
                TreeNode node = deque.poll();
                swap(node);
                if(node.left != null) deque.offer(node.left);
                if(node.right != null) deque.offer(node.right);
            }
        }
        return root;
    }
    
    public void swap(TreeNode root){
        
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
    }

**参考资料**：[226.翻转二叉树][226.]

[-226.]: https://leetcode.cn/problems/invert-binary-tree/
[ecac35d024414b26939b7d7fde345e15.png]: https://img-blog.csdnimg.cn/ecac35d024414b26939b7d7fde345e15.png
[226.]: https://programmercarl.com/0226.%E7%BF%BB%E8%BD%AC%E4%BA%8C%E5%8F%89%E6%A0%91.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE