leetcode:翻转二叉树

素颜马尾好姑娘i 2023-03-06 03:22 12阅读 0赞

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

翻转一棵二叉树。

**示例：**

输入：

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

输出：

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

我觉得这道题叫做镜像二叉树应该也可以吧。

思路：首先想到的就是相当于一个镜像，而且是左右子树进行交换位置。代码就根据简单的树的遍历,借助于临时变量作为左右子树交换的媒介，然后递归。

先写树的遍历框架：

public TreeNode invertTree(TreeNode root) {
        
            invertTree(root.left);
            invertTree(root.right);
            return root;
        }

再添加交换子树的操作，位置放在哪要考虑这道题适合哪种遍历，其实前中后序遍历都可以。所以位置也可以随便。因为交换左右子树对根没有影响。

前序：

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xfamRfZ3VsdWx1_size_16_color_FFFFFF_t_70_pic_center]

后序：

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xfamRfZ3VsdWx1_size_16_color_FFFFFF_t_70_pic_center 1]

[226.]: https://leetcode-cn.com/problems/invert-binary-tree/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xfamRfZ3VsdWx1_size_16_color_FFFFFF_t_70_pic_center]: /images/20230208/03d35d615193497293c1ebb148557cc9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xfamRfZ3VsdWx1_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20230208/e2bbf2b7eb5c46108dcf8408708309ed.png