LC114 二叉树展开为链表 · 逐题动画 · RuntimeScope

当前：LC114 · 二叉树展开为链表 · 首次出现于 Day 25 · 路径：顶栏「56天打卡」→ 点击 LC 题号 → 逐题动画

LC114 · 二叉树展开为链表 · 工程执行实验室

O(1) 原地接线 · cur / pre / oldRight

不是新建链表，而是原地改树的指针。前序顺序是根→左→右，所以当节点有左子树时，应把左子树搬到右边，再把原右子树接到左子树最右节点后面。 空间 O(1)，仅三个指针变量。

展开后：1 → 2 → 3 → 4 → 5 → 6

原地改指针 · 所有 Left = nil

核心 · 原地改指针，不是新建链表

不是新建链表，而是原地改树的指针。前序顺序是根→左→右，所以当一个节点有左子树时，应该把左子树搬到右边，再把原右子树接到左子树最右节点后面。

· 只改现有 TreeNode 的 Left / Right 指针，不分配新节点。
· 处理完每个 cur 后，cur 沿 Right 前进，已处理部分形成正确的前序右链前缀。
· 最终所有 Left 必须为 nil，Right 串起完整前序序列。

flatten 六步骤

cur = root; cur != nil
cur.Left == nil → cur = cur.Right
pre = cur.Left; while pre.Right → pre = pre.Right
oldRight = cur.Right; pre.Right = oldRight
cur.Right = cur.Left
cur.Left = nil
cur = cur.Right

O(1) 原地接线 · 主流程

1.cur 从 root 遍历；若 cur.Left == nil，则 cur = cur.Right 跳过。
2.否则找 cur.Left 子树最右 pre；oldRight = cur.Right。
3.pre.Right = oldRight → cur.Right = cur.Left → cur.Left = nil → cur = cur.Right。

1/11 · 题目定义

11 步分镜：

Step 1题目定义

展示输入树与目标前序右链

给定二叉树，原地展开为单链表：所有 Left 置 nil，Right 按前序遍历顺序连接。标准样例展开后应为 1 → 2 → 3 → 4 → 5 → 6。注意：不是新建链表，而是在原树上改指针。

不是新建链表，而是原地改树的指针。前序顺序是根→左→右，所以当一个节点有左子树时，应该把左子树搬到右边，再把原右子树接到左子树最右节点后面。
只改现有 TreeNode 的 Left / Right 指针，不分配新节点。
处理完每个 cur 后，cur 沿 Right 前进，已处理部分形成正确的前序右链前缀。
最终所有 Left 必须为 nil，Right 串起完整前序序列。

为什么正确

状态表 · cur / pre / oldRight

cur	pre	oldRight	机器状态
nil	nil	nil	读题输入树 · 目标右链

原地改指针实验室·cur = 蓝·pre = 琥珀·oldRight = 紫

Go · flatten · O(1) 原地法

1func flatten(root *TreeNode) {
2    cur := root
3    for cur != nil {
4        if cur.Left == nil {
5            cur = cur.Right
6        } else {
7            pre := cur.Left
8            for pre.Right != nil {
9                pre = pre.Right
10            }
11            oldRight := cur.Right
12            pre.Right = oldRight
13            cur.Right = cur.Left
14            cur.Left = nil
15            cur = cur.Right
16        }
17    }
18}

复杂度

时间: O(n)
空间: O(1)

每个节点最多被 cur 访问一次；找 pre 时沿左子树右链下行，每条边最多被走常数次，总计 O(n)。

只使用 cur、pre、oldRight 三个指针变量，不使用递归栈、显式栈或额外数组。仅 cur · pre · oldRight · 无递归栈

面试回答

O(1) 原地法：cur 从 root 遍历。若 cur.Left 为空则 cur = cur.Right；否则找 cur.Left 子树最右 pre，oldRight = cur.Right，执行 pre.Right = oldRight、cur.Right = cur.Left、cur.Left = nil，再 cur = cur.Right。时间 O(n)，空间 O(1)。补充：反序递归 prev 法代码短，但空间 O(h)。

递归 prev 法 · 补充（非主解）

反序递归写法：先处理 right，再处理 left，再让 root.Right = prev、root.Left = nil，prev = root。它很简洁，但空间复杂度是 O(h)（递归调用栈），不是严格 O(1)。不要把它和 O(1) 原地法混在主流程里。

var prev *TreeNode
func flatten(root *TreeNode) {
    if root == nil { return }
    flatten(root.Right)
    flatten(root.Left)
    root.Right = prev
    root.Left = nil
    prev = root
}

常见错误

错误 1：把空间写成 O(1) 却讲反序递归 prev 法

反序递归需要调用栈保存每层状态，空间是 O(h)，最坏单链 O(n)。面试若要求 O(1) 空间，应讲原地接线法。

错误 2：像新建链表一样分配节点

题目要求原地修改。所有节点都是原树上的 TreeNode，只是重连 Left/Right 指针。

错误 3：先动 cur.Left 再接 oldRight

必须先 oldRight = cur.Right 保存原右子树，再 pre.Right = oldRight，然后才能 cur.Right = cur.Left，否则丢失右子树。

错误 4：忘记最后 cur.Left = nil

展开后必须全部 Left 为 nil。只搬右链但遗留 Left 指针，不符合题意。

页面总结 · 不变量

主解 O(1) 原地接线，可观察结果 1 → 2 → 3 → 4 → 5 → 6：

1. 已处理过的节点（cur 左侧前缀）形成正确前序右链。
2. 每次接线后，cur.Right 指向「以 cur 为根的前序下一节点」。
3. 未访问部分仍保留在原树中，等待后续 cur 处理。
4. 结束时所有 Left == nil，Right 串起 1→2→3→4→5→6。

迁移练习

LC206 · 反转链表

链表指针重排的基础题；LC114 是在树上原地拉出前序右链。

LC297 · 序列化与反序列化

树↔线性表示的另一方向；LC114 只要求前序右链，不编码 null。

LC94 · 二叉树的中序遍历

Morris 遍历也能 O(1) 空间遍历树；LC114 是 O(1) 空间改结构。