LeetCode 156. 上下翻转二叉树
题目描述
题意分析
每个右孩子要么为空，要么是有左兄弟的叶子。要求沿最左路径翻转父子关系：对于原来的
parent(left, right)，让left上升为父节点，right成为它的新左孩子，原来的parent成为它的新右孩子。因此新根一定是原树最左端的节点。右孩子只需随所在层搬移，不需要继续递归处理：题目已经保证它没有子树。若一个节点没有左孩子，由于右孩子必须有左兄弟，它也不可能有右孩子。
本题并非对所有节点交换左右孩子。翻转会改变谁是谁的父节点，而且旧的父子边必须删除，否则新边和旧边可能组成环。
解法一：递归翻转最左链
核心思路
[!blue]
设当前根为
root，原左孩子为left。先递归翻转left的子树，得到新根newRoot。递归完成后，left已成为这棵新树最右端的节点，它的左右指针均已清空，正好可以接收当前层的两个节点。接下来执行
left.left = root.right、left.right = root，把原右兄弟与原父亲接到left下方。最后清空root的两条旧边；这样当前层原根也成为新树最右端的叶子节点，满足上一层继续接边的条件。这也给出了递归正确性的依据：最左叶子本身无需翻转；若左子树已按规则翻转，当前层只需补上这两条新边并删去旧边，就能得到整棵子树的正确结果。
newRoot始终是最左叶子，回溯时不能改成当前节点。
root == null时返回空树；root.left == null时返回当前叶子。其余节点一定能继续沿左链递归。
解题步骤
- 若当前节点为空或没有左孩子，直接返回它。
- 递归处理
root.left，保存返回的新根newRoot。- 通过仍指向原左孩子的
root.left，将原父节点接到它的右侧，将原右孩子接到它的左侧。- 清空
root.left和root.right，断开原来的两条边。- 返回
newRoot，让所有递归层传回同一个根。以原树
[1,2,3,4,5]为例，回溯到节点 2 时先建立4.left = 5、4.right = 2，并清空节点 2 的旧孩子；回溯到节点 1 时再建立2.left = 3、2.right = 1。根始终是节点 4。
代码实现
class Solution {
public TreeNode upsideDownBinaryTree(TreeNode root) {
if (root == null || root.left == null) {
return root;
}
TreeNode newRoot = upsideDownBinaryTree(root.left);
// 原左孩子上升：原右孩子放左边，原父节点放右边。
root.left.right = root;
root.left.left = root.right;
// 原根已经移动到新位置，必须断开旧边。
root.left = null;
root.right = null;
return newRoot;
}
}
func upsideDownBinaryTree(root *TreeNode) *TreeNode {
if root == nil || root.Left == nil {
return root
}
newRoot := upsideDownBinaryTree(root.Left)
// 原左孩子上升：原右孩子放左边，原父节点放右边。
root.Left.Right = root
root.Left.Left = root.Right
// 原根已经移动到新位置，必须断开旧边。
root.Left = nil
root.Right = nil
return newRoot
}
复杂度分析
- 时间复杂度：$O(h)$，其中 $h$ 为最左路径的节点数。只沿这条路径递归，每层进行常数次指针修改；最坏为 $O(n)$。
- 空间复杂度：$O(h)$，来自递归调用栈，最坏为 $O(n)$。
关键点总结
[!green]
- 递归返回值保存新根，
root.left保存当前层重新接边的支点，两者作用不同。- 必须先完成左子树翻转，再接上当前层；否则会提前破坏向下递归的路径。
- 当前层完成后，原根的两个孩子都为空，这既防止成环，也为上一层接边留出了位置。
解法二：迭代维护父节点与原右孩子
核心思路
[!blue]
也可以从原根沿左链向下走，在下降过程中直接翻转已访问部分。循环开始时维护三个状态：
cur是本轮待处理节点，parent是已翻转部分的根，parentRight是原父节点的右孩子。按题目的翻转规则，
cur的新左孩子应为parentRight，新右孩子应为parent。但修改前还要保存两个旧值：原左孩子用于下一轮，原右孩子用于下一轮的新左孩子。因此先保存
next = cur.left，再改写左边；接着保存原右孩子到parentRight，最后改写右边。每轮结束令parent = cur、cur = next，已经翻转的部分便向下扩展一层。初始的
parent、parentRight均为空，所以原根在第一轮自然清空两条旧边。沿左链走到空节点时，最后处理的最左叶子保存在parent中，它就是新根。
解题步骤
- 初始化
cur = root，parent与parentRight为空。- 保存原左孩子
next，将cur.left指向上一层保存的右孩子。- 保存
cur的原右孩子，供下一轮使用，再将cur.right指向parent。- 把当前节点作为新的
parent，沿next继续向下。cur为空时返回parent；若原树为空，返回值仍为空。
代码实现
class Solution {
public TreeNode upsideDownBinaryTree(TreeNode root) {
TreeNode cur = root;
TreeNode parent = null;
TreeNode parentRight = null;
while (cur != null) {
TreeNode next = cur.left;
cur.left = parentRight;
parentRight = cur.right;
cur.right = parent;
parent = cur;
cur = next;
}
return parent;
}
}
func upsideDownBinaryTree(root *TreeNode) *TreeNode {
cur := root
var parent, parentRight *TreeNode
for cur != nil {
next := cur.Left
cur.Left = parentRight
parentRight = cur.Right
cur.Right = parent
parent = cur
cur = next
}
return parent
}
复杂度分析
- 时间复杂度：$O(h)$，每个左链节点只处理一次，最坏为 $O(n)$。
- 空间复杂度：$O(1)$，只保存常数个节点指针。
关键点总结
[!green]
parentRight属于上一层，不能误用当前节点的右孩子来设置当前节点的新左边。- 每次覆盖指针前都要先保存后面仍会使用的旧值。
- 迭代法与递归法实现同一组局部连接，但通过保存状态将额外空间降为常数。
易错点总结
[!yellow]
- 把新孩子接反：原右兄弟放在新左侧，原父亲放在新右侧。
- 递归后返回
root：它已成为末端节点，返回值必须是最左叶子对应的newRoot。- 递归法保留旧边：原父亲和原左孩子会互相指向，形成环。
- 迭代法覆盖左指针后才找下一层：此时原左链入口已丢失，必须提前保存
next。- 忽略树形约束：本解法依赖“非空右孩子是有左兄弟的叶子”，不能直接用于任意二叉树。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 226. 翻转二叉树 | 简单 | 原题只交换左右孩子，本题改变父子关系，让最左节点成为新根。 |
| 206. 反转链表 | 简单 | 同样先保存下一节点再反向接边，本题沿左链操作并额外搬移右兄弟。 |