二叉树展开为链表 图解题解
从后往前接，一个指针就能把整棵树原地串成一条链。
前序遍历是「根、左、右」；如果从右、左、根倒着走，正好是前序的逆序。把这条逆序的路记成一根绳，每走到一个节点就让它的 right 指向绳子最近的那头，left 清空——相当于从尾部往前把绳子一节节接起来。最后整棵树就顺着 right 串成了一条直线，而你全程没有额外建数组，只用了一个「prev 指针」。
这道题到底在问什么
- 输入 root
- [1,2,5,3,4,null,6]
- 前序遍历
- 1 → 2 → 3 → 4 → 5 → 6
- 输出(只走 right)
- 1→2→3→4→5→6，left 全空
最优解：一步一步想明白
- 3最直白的做法:先跑一遍前序,把节点按顺序存进数组,再从头把每个 right 接到下一个。能过,但要额外 O(n) 的数组,而且没用上树本身的结构。
- 4先改根 1.right=2 → 原右子树 5 当场丢失想直接按前序从根往下接:第一步就要把 1 的 right 改成 2。可 1 的 right 原本挂着整个右子树 5。一改,通往 5 和 6 的唯一路就断了,它们彻底丢失。所以不能从前往后改。
- 5换个方向。我们倒着接:遍历顺序是右、左、根,刚好是前序的逆序。再带一个 prev 指针,记住「当前节点在最终链里的下一个」。处理到谁,就让它的 right 指向 prev、left 清空。
- 6prev = 6(链尾)逆前序最先抵达的是 6,它是前序里的最后一个,后面没人,right 不用动。我们让 prev 记住 6,它就是接下来 5 应该指向的下一个。
- 75.right = prev(6),5.left = 空,prev 前移到 5轮到 5。把 5 的 right 接到 prev,也就是 6,得到 5→6;再把 5 的 left 清空。然后 prev 前移到 5,准备给下一个节点当后继。链现在是 5→6。
- 84.right = prev(5),4.left = 空,prev = 4同一个动作再来一次。轮到 4:它的 right 接到 prev,现在 prev 是 5,于是 4→5→6;left 清空;prev 前移到 4。链又往前长了一节。
- 93.right = prev(4),3.left = 空,prev = 3轮到 3。它的 right 接到 prev,现在 prev 是 4,于是 3→4→5→6;left 清空;prev 前移到 3。还是同一套动作。
- 102.right = prev(3),2.left = 空,prev = 2再轮到 2。它的 right 接到 prev,现在 prev 是 3,链变成 2→3→4→5→6;left 清空;prev 前移到 2。注意全程都是同一套动作,只是 prev 在往前滑。
- 111.right = prev(2),1.left = 空 → 全链 1→…→6最后一步处理根 1:它的 right 接到 prev(2),left 清空。整条链 1→2→3→4→5→6 成型。回头看:正因为倒着接,轮到 1 时它的右子树 5 早就被串进链里了,根本不会丢。
- 12left 全空,right 串成 1→2→3→4→5→6展开完成。所有 left 都空了,六个节点靠 right 串成一条链,顺序正好是前序遍历 1、2、3、4、5、6。这就是二叉树展开为链表。
- 15一句话本质:按右、左、根逆序处理,每到一个节点就把它的 right 接到 prev、left 清空、再让 prev 等于自己。倒着接,所以用到 prev 时它一定已经就位。
- 17只接 right、没清 left → 1 还挂着旧左孩子 2演一下漏清 left 的坑。如果处理 1 时只接了 right、没把 left 设空,那 1 还挂着原来的左孩子 2。这就不是一条单链表了,从 1 还能往 left 拐,判题直接挂。所以 left 清空这步不能省。
- 22记住这套「逆序遍历 + prev 指针穿线」。它能迁移到很多树题:把二叉搜索树转成累加树(538,逆中序+prev)、二叉树展开为环、原地重构指针。点开树专题接着练,有不懂随时问 AI 助教小欧。
⚠️ 容易写错的地方
✗ 错：按正前序从根往下改 right
✓ 对：逆前序:右 → 左 → 根
从根改 right 会覆盖掉指向右子树的唯一引用,右子树当场丢失
✗ 错：只改 right,忘了 left 清空
✓ 对：每个节点都要 node.left = 空
题目要求是单链表,残留的 left 会让结构不是一条链
✗ 错：递归写成先左后右
✓ 对：必须先递归右、再递归左
prev 要按前序逆序更新,先左会让接出来的顺序错乱
完整代码（Python / C++ / Java）
Python
class Solution:
def flatten(self, root):
self.prev = None # 当前节点的前序后继
def dfs(node):
if not node:
return
dfs(node.right) # 先右
dfs(node.left) # 再左
node.right = self.prev # 根:right 接到 prev
node.left = None # left 清空
self.prev = node # prev 前移到自己
dfs(root)C++
class Solution {
TreeNode* prev = nullptr;
void dfs(TreeNode* node) {
if (!node) return;
dfs(node->right); // 先右
dfs(node->left); // 再左
node->right = prev; // 根:right 接到 prev
node->left = nullptr; // left 清空
prev = node; // prev 前移
}
public:
void flatten(TreeNode* root) { dfs(root); }
};Java
class Solution {
private TreeNode prev = null;
public void flatten(TreeNode root) {
if (root == null) return;
flatten(root.right); // 先右
flatten(root.left); // 再左
root.right = prev; // 根:right 接到 prev
root.left = null; // left 清空
prev = root; // prev 前移
}
}套路模板 · 逆序遍历 + prev 穿线(三语言骨架)
# 套路:逆序 DFS,用 prev 边走边把指针接好
self.prev = None
def dfs(node):
if not node: return
dfs(node.???) # 先递归「后处理」的那一侧
dfs(node.???) # 再递归另一侧
node.??? = self.prev # 把当前指针接到 prev
# 清空不用的另一指针(如 node.left = None)
self.prev = node # prev 前移到自己// 套路:逆序 DFS + prev 穿线
TreeNode* prev = nullptr;
void dfs(TreeNode* node) {
if (!node) return;
dfs(node->???); // 先递归「后处理」侧
dfs(node->???); // 再递归另一侧
node->??? = prev; // 接到 prev
// 清空另一指针
prev = node; // prev 前移
}// 套路:逆序 DFS + prev 穿线
TreeNode prev = null;
void dfs(TreeNode node) {
if (node == null) return;
dfs(node.???); // 先递归「后处理」侧
dfs(node.???); // 再递归另一侧
node.??? = prev; // 接到 prev
// 清空另一指针
prev = node; // prev 前移复杂度
时间复杂度
O(n)
每个节点恰好访问并改一次指针 → n 次操作
空间复杂度
O(h)
只有递归栈,h=树高;最坏退化成链时 O(n)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 二叉树展开为链表 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么用逆前序,不用正常前序?+
正前序处理当前节点时,它的右子树还没处理,直接改 right 会覆盖掉指向右子树的唯一引用、把右子树弄丢。逆前序(右→左→根)保证轮到当前节点时,它前序的后继 prev 已接好,直接 cur.right=prev 即可。
展开后 left 怎么处理?+
全部置空。题目要求是单链表,所有节点只通过 right 串联,残留的 left 会让它不是一条链,所以每个节点都要 left=空。
能做到 O(1) 额外空间吗?+
能,用 Morris 式迭代。对每个有左子树的节点,找它左子树的最右节点,把当前的右子树接到那个最右节点后面,再把整个左子树挪到右边、left 清空,然后往右走。不用递归栈,空间 O(1)。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。