226. 翻转二叉树
题目描述
给你一棵二叉树的根节点 root，翻转这棵二叉树，并返回其根节点。
翻转：交换每个节点的左右子树。
示例
示例 1：
输入: root = [4,2,7,1,3,6,9]
输出: [4,7,2,9,6,3,1]
4 4
/ \ / \
2 7 -> 7 2
/ \ / \ / \ / \
1 3 6 9 9 6 3 1
示例 2：
输入: root = [2,1,3]
输出: [2,3,1]
解题思路
第一步：理解问题本质
翻转二叉树 = 交换每个节点的左右子节点。
这是一个递归结构的问题：整棵树的翻转 = 左子树翻转 + 右子树翻转 + 交换左右子树。
第二步：暴力解法 - 复制新树
遍历原树，创建新树，左右子树交换位置。
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
# 空节点没有左右子树可换，直接返回
if not root:
return None
# 复制一份当前节点，原树保持不动
new_root = TreeNode(root.val)
# 左孩子接「翻转后的右子树」、右孩子接「翻转后的左子树」，这就是翻转
new_root.left = self.invertTree(root.right)
new_root.right = self.invertTree(root.left)
return new_root
为什么不够好：需要创建新节点，空间复杂度 O(n)。
第三步：优化解法 - 原地递归
直接修改原树的指针，无需创建新节点。
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
# 递归出口：空节点无处可翻，原样返回
if not root:
return None
# 先递归翻转
# 两个结果必须先存下来：一旦改写 root.left，就再也找不到原来的左子树
left = self.invertTree(root.left)
right = self.invertTree(root.right)
# 再交换
root.left = right
root.right = left
# 当前节点已翻转完，返回给父节点接链
return root
第四步：最优解法 - 递归或迭代
递归最简洁，迭代（BFS）可以避免栈溢出。
完整代码实现
算法可视化 · 逐帧回放这道题的代码57 帧 · 录制输入 [4,2,7,1,3,6,9]
from typing import Optional
class Solution:
"""
翻转二叉树 - 递归法
核心思路：
递归地翻转左右子树，然后交换它们。
时间复杂度：O(n)
空间复杂度：O(h) - h 为树高度
"""
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
# 递归翻转左右子树
left = self.invertTree(root.left)
right = self.invertTree(root.right)
# 交换左右子树
root.left = right
root.right = left
return root
示例推演
以 [4,2,7,1,3,6,9] 为例：
4
/ \
2 7
/ \ / \
1 3 6 9
递归过程：
invertTree(4)invertTree(2)invertTree(1)-> 返回 1invertTree(3)-> 返回 3- 交换：2 的左=3，右=1
- 返回 2
invertTree(7)invertTree(6)-> 返回 6invertTree(9)-> 返回 9- 交换：7 的左=9，右=6
- 返回 7
- 交换：4 的左=7，右=2
- 返回 4
结果：
4
/ \
7 2
/ \ / \
9 6 3 1
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 复制新树 | O(n) | O(n) | 需要额外空间 |
| 原地递归 | O(n) | O(h) | h 为树高度 |
| BFS 迭代 | O(n) | O(w) | w 为树的最大宽度 |
易错点总结
1. 忘记返回 root
错误：
# 子树确实已经原地翻好，但本函数返回 None，父节点接不到它
self.invertTree(root.left)
self.invertTree(root.right)
# 没有 return root
正确：
# 翻转虽然是原地改指针，但调用方要靠返回值接住这棵子树
return root # 必须返回根节点
2. 交换顺序错误
先交换再递归也可以，但要保持一致：
# 方案一：先递归，后交换
# 拿到的是两棵已经翻转好的子树，最后对调它们的位置
left = self.invertTree(root.left)
right = self.invertTree(root.right)
root.left, root.right = right, left
# 方案二：先交换，后递归
# 交换后 root.left 已经是原右子树，对它递归同样能翻转
root.left, root.right = root.right, root.left
self.invertTree(root.left)
self.invertTree(root.right)
3. 空节点处理
# 空节点上取 .left / .right 会报错，先挡住；返回 None 而不是 root
if not root:
return None # 不是 return root
扩展思考
1. 翻转 N 叉树
559. N 叉树的最大深度 类似思路，交换 children 列表。
2. 相关题目
- 101. 对称二叉树 - 判断树是否对称
- 100. 相同的树 - 判断两棵树是否相同
- 226. 翻转二叉树 - 本题