LeetCode 226. 翻转二叉树
目录
题目描述
题意分析
给定二叉树的根节点，把整棵树左右镜像后返回根。所谓镜像，是每一个节点的左右孩子都要对调——不只是根节点这一层。以样例
[4,2,7,1,3,6,9]为例，仅交换根的两个孩子得到的是[4,7,2,6,9,1,3]，而正确答案是[4,7,2,9,6,3,1]：深层的1,3与6,9也各自换了位置。题目允许原地修改并返回原根，不要求新建一棵树；节点值本身不动，动的只是左右指针的指向。
规模很小（节点数不超过 100），任何遍历一遍的做法都绰绰有余。边界只有一个：
root可能为空，空树的镜像还是空树。
解法：递归交换左右子树
核心思路
问题关键：镜像不是只交换根节点，而是每个节点都要交换左右孩子。左右子树仍是同一个问题，因此递归最自然。
定义
invertTree(node)：返回以node为根、已经完全翻转的子树。递归得到翻转后的左右子树，再交叉挂回当前节点；空节点直接返回。由定义可知，两棵子树正确翻转且位置互换后，当前子树也一定正确，递归因此成立。若树很深、担心递归栈，可改用队列或显式栈遍历；每访问一个节点就交换其左右孩子，核心操作不变。
解题步骤
root == null时返回null，作为递归出口。- 分别递归翻转原左子树和原右子树，并保存两个返回值。
- 将翻转后的右子树挂到
root.left，翻转后的左子树挂到root.right。- 返回
root，供上一层继续连接。例如节点
2的孩子是1、3，递归返回后挂成3、1；每个节点都做同样的交换，整棵树自然完成镜像。
代码实现
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
// 左右子树分别翻转后，再交换挂回当前节点。
TreeNode left = invertTree(root.left);
TreeNode right = invertTree(root.right);
root.left = right;
root.right = left;
return root;
}
}
func invertTree(root *TreeNode) *TreeNode {
if root == nil {
return nil
}
// 递归翻转左右子树，再在当前节点完成镜像交换。
left := invertTree(root.Left)
right := invertTree(root.Right)
root.Left = right
root.Right = left
return root
}
复杂度分析
- 时间复杂度：$O(n)$。每个节点恰好被访问一次，每次只做常数次指针操作。
- 空间复杂度：$O(h)$。递归栈深度等于树高，平衡时为 $O(\log n)$，链状退化时最坏 $O(n)$。
关键点总结
- 先明确递归函数的承诺：返回“已经翻转完成”的当前子树。
- 当前层只负责交叉连接两个递归结果，子树内部交给递归处理。
- 面试时能补充：递归空间取决于树高；极深树可换成显式栈或队列。
易错点总结
- 覆盖了原孩子再读取：若先写
root.left = invertTree(root.right)，再递归root.left，[4,2,7]会重复处理原右子树并丢掉节点2。先保存两个递归结果再赋值。- 只交换根节点：
[4,2,7,1,3,6,9]会错误得到[4,7,2,6,9,1,3]，深层节点并未镜像。- 漏掉空节点出口：空树会触发空指针异常；叶子节点的空孩子也依赖这个出口结束递归。
- 交换节点值而不是孩子指针：镜像改变的是树结构，只换值无法保证子树位置正确。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 剑指 Offer 27. 二叉树的镜像 | 简单 | 同一题的另一版本，可练习先交换再递归的写法 |
| 101. 对称二叉树 | 简单 | 不修改树，双指针同步递归判断镜像相等 |
| 951. 翻转等价二叉树 | 中等 | 每个节点可选翻或不翻，递归带分支讨论 |