LeetCode 156. 上下翻转二叉树
目录
题目描述
题意分析
给定一棵满足特殊约束的二叉树：每个右孩子要么为空，要么是一个拥有左兄弟的叶子节点。要求沿着整棵树的最左路径逐层翻转，使原来的最左叶子成为新根。
对任意局部结构
parent(left, right)，翻转后原来的left上升：right变成它的新左孩子，parent变成它的新右孩子。也就是把
parent.left = left, parent.right = right改成
left.left = right, left.right = parent。题目的树形约束非常关键：右孩子没有自己的子树，因此把它搬到左孩子下面不会丢失后续结构；若允许右孩子继续向下生长，这套局部旋转就不足以覆盖所有节点。
以
[1,2,3,4,5]为例，原树的最左链是1 → 2 → 4。翻转后4成为新根，4.left = 5、4.right = 2，再令2.left = 3、2.right = 1，结果为[4,5,2,null,null,3,1]。
解法一：递归翻转最左链
核心思路
递归函数的返回值始终表示：以当前节点为根的子树翻转完成后，整棵新树的根节点。这个返回值一旦在最左叶子处确定，回溯过程中必须原样向上传递。
先递归翻转
root.left。递归返回时，原来的左孩子root.left已经位于新树最右侧，正好可以接收两个新孩子：把原右孩子挂到它的左边，把原根挂到它的右边。完成新连接后，必须把
root.left和root.right同时置空。原根已经被挂到新位置，旧边若不清除，会让同一个节点拥有多条父边，甚至形成环。递归基是
root == null || root.left == null。空树直接返回空；没有左孩子时，当前节点就是最左端，也就是翻转后的新根。题目约束保证此时不会存在一个孤立的右子树需要继续处理。
解题步骤
- 向左递归到底：调用
upsideDownBinaryTree(root.left)，获得最终的新根newRoot。- 建立新左边：执行
root.left.left = root.right，把原来的右兄弟挂到原左孩子的左侧。- 建立新右边：执行
root.left.right = root，把原父节点挂到原左孩子的右侧。- 断开旧边：将
root.left、root.right置空。- 返回同一个新根：所有递归层都返回
newRoot，不能返回当前的root。用
[1,2,3,4,5]走一遍：递归先到节点 4 并返回 4；回到节点 2 时执行4.left = 5、4.right = 2，再清空节点 2 的旧孩子；回到节点 1 时，此刻原左孩子节点 2 已是新树最右端，执行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$ 是最左路径长度，每层只访问和改写一次；在最坏的退化树中 $h = n$，因此也可写成 $O(n)$。
- 空间复杂度：$O(h)$，来自递归调用栈；最坏为 $O(n)$。
关键点总结
- 递归返回值是整棵翻转后子树的新根，不是当前层的新父节点。
- 必须先递归再改边；下降阶段仍需要完整的原始左链。
root.left在回溯时仍指向原左孩子，而该节点恰好是已翻转子树的最右端，因此可以直接作为重新接边的支点。- 两条旧边都要清空，树的指针改写题必须同时考虑“建立新边”和“删除旧边”。
解法二：迭代维护父节点与原右孩子
核心思路
递归回溯实际只依赖三份信息：当前节点
cur、已经翻转好的父节点parent、以及上一层暂存的原右孩子parentRight。把这三份状态显式保存，就能沿最左链从上到下原地翻转，省掉递归栈。循环不变量是：
parent是已经翻转部分的根，parentRight应成为cur的新左孩子，而cur.left仍指向下一轮要处理的节点。每轮必须先保存next = cur.left，再覆盖cur.left。
解题步骤
- 初始化
cur = root、parent = null、parentRight = null。- 保存下一层原左孩子
next = cur.left。- 令
cur.left = parentRight，接上上一层保存的原右孩子。- 先保存本层原右孩子到
parentRight，再令cur.right = parent。- 推进
parent = cur、cur = next；循环结束时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)$，只维护常数个节点指针。
关键点总结
next必须在覆盖cur.left之前保存，否则剩余左链会丢失。parentRight的含义是“上一层原来的右孩子”，它在当前层成为新左孩子。- 四个赋值的顺序就是迭代法的核心：保存左链 → 接新左边 → 保存原右边 → 接新右边。
解法对比
| 解法 | 时间复杂度 | 额外空间 | 面试取舍 |
|---|---|---|---|
| 递归 | $O(h)$ | $O(h)$ | 结构与题意最贴合，容易证明，推荐先讲 |
| 迭代 | $O(h)$ | $O(1)$ | 空间更优，但三个指针的语义和赋值顺序更容易写错 |
易错点总结
- 把新左右孩子接反：样例中节点 4 的新左孩子应是原右兄弟 5，新右孩子才是原父节点 2；写反会得到另一棵树。
- 递归前就修改
root.left：会丢掉通往最左叶子的入口，[1,2,3,4,5]无法继续访问节点 4。- 忘记清空原根的孩子：节点 1、2 仍保留旧指针，新旧边同时存在，结果不再是一棵合法树。
- 返回当前
root：样例最终会返回节点 1，而正确的新根是节点 4。递归各层必须返回同一个newRoot。- 把本题当成 226 的左右子树交换：本题改变父子关系并让最左叶子上升，不是对每个节点交换左右孩子。
- 忽略输入约束：若出现“只有右孩子且右孩子还有子树”的普通二叉树，这套算法并不保证得到题目定义的翻转结果；面试时应主动说明算法依赖题设结构。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 206. 反转链表 | 简单 | 同样需要先保存后继再原地反转指针，是迭代写法的直接类比 |
| 114. 二叉树展开为链表 | 中等 | 原地改写树指针，同时必须避免丢失尚未处理的子树 |
| 226. 翻转二叉树 | 简单 | 只交换每个节点的左右孩子，可对照本题为何会改变父子关系 |
| 430. 扁平化多级双向链表 | 中等 | 多指针结构重连，重点同样是保存入口并清除旧边 |