题目描述
思路解析动画文字版
最直白的做法:先跑一遍前序,把节点按顺序存进数组,再从头把每个 right 接到下一个。能过,但要额外 O(n) 的数组,而且没用上树本身的结构。
正前序的陷阱 · 改 1 的 right 会丢右子树：想直接按前序从根往下接:第一步就要把 1 的 right 改成 2。可 1 的 right 原本挂着整个右子树 5。一改,通往 5 和 6 的唯一路就断了,它们彻底丢失。所以不能从前往后改。
换个方向。我们倒着接:遍历顺序是右、左、根,刚好是前序的逆序。再带一个 prev 指针,记住「当前节点在最终链里的下一个」。处理到谁,就让它的 right 指向 prev、left 清空。
灵魂帧① · 最先处理最右的 6,prev 记住它：逆前序最先抵达的是 6,它是前序里的最后一个,后面没人,right 不用动。我们让 prev 记住 6,它就是接下来 5 应该指向的下一个。
灵魂帧② · 处理 5:5.right 接到 prev(6)：轮到 5。把 5 的 right 接到 prev,也就是 6,得到 5→6;再把 5 的 left 清空。然后 prev 前移到 5,准备给下一个节点当后继。链现在是 5→6。
灵魂帧③ · 处理 4:4.right 接到 prev(5)：同一个动作再来一次。轮到 4:它的 right 接到 prev,现在 prev 是 5,于是 4→5→6;left 清空;prev 前移到 4。链又往前长了一节。
灵魂帧④ · 处理 3:3.right 接到 prev(4)：轮到 3。它的 right 接到 prev,现在 prev 是 4,于是 3→4→5→6;left 清空;prev 前移到 3。还是同一套动作。
灵魂帧⑤ · 处理 2:2.right 接到 prev(3)：再轮到 2。它的 right 接到 prev,现在 prev 是 3,链变成 2→3→4→5→6;left 清空;prev 前移到 2。注意全程都是同一套动作,只是 prev 在往前滑。
灵魂帧⑥ · 最后接上根 1,整链成型：最后一步处理根 1:它的 right 接到 prev(2),left 清空。整条链 1→2→3→4→5→6 成型。回头看:正因为倒着接,轮到 1 时它的右子树 5 早就被串进链里了,根本不会丢。
完成 · 只剩 right 的前序链表：展开完成。所有 left 都空了,六个节点靠 right 串成一条链,顺序正好是前序遍历 1、2、3、4、5、6。这就是二叉树展开为链表。
一句话本质:按右、左、根逆序处理,每到一个节点就把它的 right 接到 prev、left 清空、再让 prev 等于自己。倒着接,所以用到 prev 时它一定已经就位。
雷区实演 · 忘清 left 会怎样：演一下漏清 left 的坑。如果处理 1 时只接了 right、没把 left 设空,那 1 还挂着原来的左孩子 2。这就不是一条单链表了,从 1 还能往 left 拐,判题直接挂。所以 left 清空这步不能省。
边界三连：边界先看三种:空树直接返回;单节点本来就是链;只有左孩子时,要把左孩子搬到 right、把 left 清空——这正是展开的核心动作。
面试追问：三个高频追问:为什么逆前序、left 怎么办、能不能 O(1) 空间(Morris)。把动画里的状态和方向讲成自己的话。
迁移阶梯：记住这套「逆序遍历 + prev 指针穿线」。它能迁移到很多树题:把二叉搜索树转成累加树(538,逆中序+prev)、二叉树展开为环、原地重构指针。点开树专题接着练,有不懂随时问 AI 助教小欧。
参考代码
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)复杂度
- 时间复杂度：O(n)，每个节点恰好访问并改一次指针 → n 次操作
- 空间复杂度：O(h)，只有递归栈,h=树高;最坏退化成链时 O(n)
可套用的代码模板
这是挖空骨架,不是抄参考代码。本题填:先 dfs(右)、再 dfs(左),node.right=prev、node.left 清空。换成累加树(538)就改成逆中序——先 dfs(右)、再在中间累加并写回 node.val、最后 dfs(左);顺序从右→左→根变成右→根→左,但同样是逆序 + 一个 prev(这里 prev 换成累加和 sum)。
# 套路:逆序 DFS,用 prev 边走边把指针接好self.prev = Nonedef dfs(node): if not node: return dfs(node.???) # 先递归「后处理」的那一侧 dfs(node.???) # 再递归另一侧 node.??? = self.prev # 把当前指针接到 prev # 清空不用的另一指针(如 node.left = None) self.prev = node # prev 前移到自己易错点
面试追问把动画讲成自己的话
追问为什么用逆前序,不用正常前序?
追问展开后 left 怎么处理?
追问能做到 O(1) 额外空间吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
合并二叉树
LeetCode 617 · 简单 · 沿着 树 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题