# 226. 翻转二叉树

# 题目描述

给你一棵二叉树的根节点 root，翻转这棵二叉树，并返回其根节点。

示例 1：

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

1
2

示例 2：

输入：root = []
输出：[]

1
2

# 思路

整棵树翻转看着复杂，到每个节点上到底要做什么？交换当前节点的左右孩子，再对所有节点重复这个动作就行。这是代码随想录原题里最重要的观察。

用前序遍历，先交换，再递归处理交换后的左、右子树。递归函数传入并返回当前节点；空节点直接返回；单层逻辑是交换、递归左、递归右。后序也可以做，中序按普通写法容易把孩子重复交换。

# 模拟过程

主站的图把整棵树翻转前后的结构放在一起：

以根节点 4 为例，先交换孩子 2 和 7；再递归到新左子树的 7，交换孩子 6 和 9；最后处理新右子树的 2，交换孩子 1 和 3。最终层序结果是 [4,7,2,9,6,3,1]。

# 解题代码

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr) return root;
        swap(root->left, root->right); // 中：每个节点只交换一次
        invertTree(root->left);        // 左
        invertTree(root->right);       // 右
        return root;
    }
};

1
2
3
4
5
6
7
8
9
10

# 复杂度分析

时间复杂度：O(n)，访问每个节点一次。
空间复杂度：O(h)，递归栈占用树高 h。

# 其他语言

# Python3

class Solution:
    def invertTree(self, root):
        if root is None:
            return None
        root.left, root.right = root.right, root.left
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root

1
2
3
4
5
6
7
8

# Java

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

1
2
3
4
5
6
7
8
9
10
11

# Go

func invertTree(root *TreeNode) *TreeNode {
    if root == nil { return nil }
    root.Left, root.Right = root.Right, root.Left
    invertTree(root.Left)
    invertTree(root.Right)
    return root
}

1
2
3
4
5
6
7

# JS

var invertTree = function(root) {
    if (root === null) return null;
    [root.left, root.right] = [root.right, root.left];
    invertTree(root.left);
    invertTree(root.right);
    return root;
};