LeetCode 226. 翻转二叉树
题目描述
题意分析
给定二叉树的根节点，把整棵树变成左右镜像，并返回翻转后的根节点。镜像意味着每个节点的左、右子树都交换位置，子树内部也要继续进行同样的翻转。
翻转改变的是节点连接关系，节点及其数值保持不变。空树翻转后仍为空，只有一个节点时也保持原样；只交换根节点的两个孩子，无法完成更深层结构的镜像。
解法：递归交换左右子树
核心思路
[!blue]
一棵树的镜像可以由两部分组成：原右子树的镜像放到左侧，原左子树的镜像放到右侧。子树仍然是二叉树，所以“求子树镜像”可以交给同一个递归函数完成。
明确
invertTree(root)的含义：原地翻转以root为根的整棵子树，并返回这棵子树的根节点。若root为空，直接返回空；这是空树的答案，也是叶子节点继续递归时的结束条件。对非空节点，先递归翻转原左子树，将返回值保存为
left；再翻转原右子树，保存为right。两个返回值对应的子树内部都已经完成镜像，当前层只需令root.left = right、root.right = left，就完成了整棵当前子树的翻转。先保存两个结果再覆盖孩子指针，是为了保留原来两侧的入口。若先覆盖其中一侧，再通过被覆盖后的指针访问另一侧，就可能重复处理同一棵子树并丢失另一棵。完成交换后返回原来的
root，让上一层继续连接；递归逐层返回时，整棵树自然都完成镜像。
解题步骤
- 若根节点为空，直接返回空。
- 递归翻转原左、右子树，将返回的根节点分别保存为
left、right。- 将
right挂到当前节点的左侧，将left挂到右侧。- 返回当前根节点，供上一层连接已经翻转完成的子树。
代码实现
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)$，其中
n为节点数。每个节点恰好访问一次，每次只做常数次指针操作。- 空间复杂度：$O(h)$，其中
h为树高。递归栈同时保存一条根到叶子的路径，平衡树为 $O(\log n)$，链状树最坏为 $O(n)$；原地修改并不意味着递归栈也只占常量空间。
关键点总结
[!green]
- 先明确递归函数的承诺：返回“已经翻转完成”的当前子树。
- 当前层只负责交叉连接两个递归结果，子树内部交给递归处理。
易错点总结
[!yellow]
- 在保存原孩子之前覆盖指针，会丢失另一侧的入口；应先得到并保存两个递归结果，再交换连接。
- 只交换根节点的左右孩子，子树内部仍保持原方向，不能得到整棵树的镜像。
- 漏掉空节点出口，不仅无法处理空树，访问叶子的空孩子时也会发生错误。
- 交换两个孩子的数值不能代替交换子树，镜像需要移动的是整个子树的连接位置。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 101. 对称二叉树 | 简单 | 对称性可以看作原树与镜像相同，本题实际生成镜像结构。 |
| 156. 上下翻转二叉树 | 中等 | 原题把最左链向上翻转并改变父子关系，本题只在每个节点交换左右孩子。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！