018 · Invert Binary Tree

algorithm

Published

May 20, 2026

My First Thoughts

这道题是第一次接触二叉树。

刚看完题，第一反应是：

翻转其实就是把每个节点的左右孩子互换吧？

也就是说，整棵树的”父子关系”其实没有变：

节点 4 还是它两个孩子的父亲
节点 2 还是它两个孩子的父亲

变的只是：原来在左边的孩子，现在跑到右边去了；原来在右边的，跑到左边去了。

所以这是一个局部交换的问题，每个节点只需要做一件事：

node.left 和 node.right 互换

但有一个地方要注意：不能只换根节点。

比如根节点 4 的左右孩子互换以后，节点 7 跑到左边来了，但 7 自己的孩子 6、9 还保持原样。这两个孩子也得换一次。

所以做法是：树里每一个节点都要做一次左右互换。

第一次写代码时，很自然会想：

先检查这个节点有没有孩子，有的话再换。

按这个思路，代码大致是：

def invertTree_with_check(root):
    if root is None:
        return None

    # 先判断有没有孩子，有才交换
    if root.left is not None or root.right is not None:
        root.left, root.right = root.right, root.left

    # 再分别处理左右子树
    invertTree_with_check(root.left)
    invertTree_with_check(root.right)

    return root

这里用到了 Python 的元组解包：

a, b = b, a

一行就完成两个变量互换，不需要中间变量。

Why That Is Not Enough

上面的代码能跑对，但有两个地方可以变得更简洁。

第一，if root.left is not None or root.right is not None 这个判断完全可以省掉。

因为即使两边都是 None，互换也不会出错：

# 假设 root.left = None, root.right = None
root.left, root.right = root.right, root.left
# 结果：root.left = None, root.right = None  ← 等于什么都没做

# 假设 root.left = None, root.right = 7
root.left, root.right = root.right, root.left
# 结果：root.left = 7, root.right = None  ← 完全正确

None 跟任何东西交换都是合法的，所以这个判断纯属多余。

第二，把”处理当前节点”放在中间，看起来有点乱。

更自然的递归写法是这样的顺序：

如果节点是空，直接返回
递归翻转左子树
递归翻转右子树
交换当前节点的左右孩子
返回当前节点

或者把第 2、3、4 步换个顺序——先交换再递归 也是对的。因为这道题里”交换”和”递归子树”互不影响，前后顺序都不会影响最终结果。

Final Idea

用递归解决这道题。

递归的核心思想是：把大问题拆成同样形状的小问题。

对于这道题，“翻转一整棵树” 可以拆成：

翻转(树) = 翻转(左子树) + 翻转(右子树) + 交换当前节点的左右孩子

左子树和右子树本身也是树，所以可以用同一个函数去处理它们。

递归终止条件：当节点是 None 时，直接返回 None。这是树的”叶子之外”，再往下就没东西可翻转了。

以这棵树为例：

递归调用大致是这样展开的：

invert(4)
├── invert(2)
│   ├── invert(1) → None
│   ├── invert(3) → None
│   └── 交换：2.left=3, 2.right=1
├── invert(7)
│   ├── invert(6) → None
│   ├── invert(9) → None
│   └── 交换：7.left=9, 7.right=6
└── 交换：4.left=7, 4.right=2

最后整棵树变成：

Why It Works

递归之所以适合树，是因为树本身就是递归定义的：

一棵树 = 一个根节点 + 一棵左子树 + 一棵右子树

而左子树、右子树本身又都是树。

这种”自己包含自己”的结构，天然适合用递归处理：函数只需要解决根节点的事，剩下的子树交给函数自己去递归。

这道题里：

根节点要做的事是：交换 left 和 right
左子树和右子树要做的事，跟根节点完全一样

所以递归调用同一个函数即可，每个节点都会被访问到一次，每个节点都会做一次交换。

Code

def invertTree(root):
    if root is None:
        return None

    invertTree(root.left)
    invertTree(root.right)

    root.left, root.right = root.right, root.left

    return root

Complexity

Time	\(O(n)\) — 每个节点恰好被访问一次
Space	\(O(h)\) — 递归调用栈的深度等于树的高度 `h`，最坏情况下（树退化成一条链）是 \(O(n)\)

Takeaway

翻转二叉树不是把树整体掀过来，而是让每个节点都把自己的左右孩子互换一次。树是递归定义的结构，所以用递归写最自然：函数只管根节点的交换，左右子树交给函数自己。

← Quiz