本文概览：本文以LeetCode题目"二叉树展开为链表"为例，讲解如何原地将二叉树按先序遍历展开为链表，通过"左子树最右节点接右子树"的迭代技巧实现 O(1) 额外空间
一、题目
二、题目分析
题目要求：把一棵二叉树按先序遍历的顺序展开成一个单链表，用 right 指针作为 next，left 全部置为 null
比如：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| 1
/ \
2 5
/ \ \
3 4 6
展开为（先序遍历顺序）：1 → 2 → 3 → 4 → 5 → 6
1
\
2
\
3
\
4
\
5
\
6
|
思路概览
最优解是迭代法，O(1) 额外空间，O(n) 时间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| public void flatten(TreeNode root) {
TreeNode cur = root;
while (cur != null) {
if (cur.left != null) {
TreeNode pre = cur.left;
while (pre.right != null) {
pre = pre.right;
}
pre.right = cur.right;
cur.right = cur.left;
cur.left = null;
}
cur = cur.right;
}
}
|
思路简要说明
核心思路就三步，对每个有左子树的节点重复执行：
- 找到左子树的最右节点——它是左子树先序遍历的最后一个节点
- 把右子树挂到这个最右节点的右侧——这样右子树就不会丢失
- 把左子树挂到当前节点的右侧，左子树置空——保持先序顺序
三、思路详解
暴力解法：先序遍历 + 重新拼接
先序遍历一遍二叉树，把遍历到的节点存入一个 List 中，然后遍历 List，把每个节点的 left 置空、right 指向下一个节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public void flatten(TreeNode root) {
List<TreeNode> list = new ArrayList<>();
preorder(root, list);
for (int i = 0; i < list.size() - 1; i++) {
list.get(i).left = null;
list.get(i).right = list.get(i + 1);
}
}
private void preorder(TreeNode root, List<TreeNode> list) {
if (root == null) return;
list.add(root);
preorder(root.left, list);
preorder(root.right, list);
}
|
缺点：
- 需要 O(n) 额外空间存储 List
- 先序遍历一遍，再遍历 List 赋值一遍，相当于遍历了两遍二叉树
为什么不能直接边遍历边赋值？
你可能想：那能不能直接先序遍历，每遍历一个节点就把它的 right 指向下一个节点？
但是这样行不通。看下面这个例子：
1
2
3
4
5
6
7
8
9
| 1
/ \
2 5
先序遍历顺序：1 → 2 → 5
如果直接赋值 right：
遍历到 1：把 1.right 指向 2（那是左子树原来的 2，没问题）
遍历到 2：那 5 怎么办？原来的 1.right 是 5，但已经被覆盖成 2 了，5 丢了！
|
核心问题：直接赋值会破坏树的结构。当你把当前节点的 right 改成下一个节点时，原来的右子树就丢失了，无法再找到
关键观察：两个确定的指针关系
先想一个问题：按先序遍历的顺序，对于一个有左子树的节点来说，哪些指针关系是确定的？
观察 1：当前节点的下一个节点，一定是左子树的根节点
先序遍历是"根→左→右"，所以只要当前节点有左子树，下一个要遍历的肯定是左子树的根节点
1
2
3
4
5
| 1
/ \
2 5
1 的下一个节点 = 2（左子树的根）
|
观察 2：左子树中最后一个遍历到的节点，一定是左子树的最右节点，它的下一个节点是右子树的根节点
先序遍历处理完左子树之后，就会处理右子树。而左子树按"根→左→右"的顺序遍历，最后一个节点就是左子树的最右节点
1
2
3
4
5
6
7
8
9
| 1
/ \
2 5
/ \ \
3 4 6
1 的左子树： 2 → 3 → 4
最右节点 = 4
4 的下一个节点 = 5（右子树的根）
|
这两个观察给了我们一个关键的信息：
对于当前节点 cur，如果它有左子树：
cur.right 应该指向 cur.left（左子树根节点）cur.left 的最右节点的 right 应该指向 cur.right（原来的右子树）
这就是迭代法的理论基础
核心技巧：左子树最右节点接右子树
基于上面的观察，迭代法的核心操作可以概括为：
1
2
3
4
5
6
| 对每个有左子树的节点 cur：
1. 找到左子树的最右节点 pre（左子树最后一个节点）
2. 把 cur 的右子树挂到 pre 的右侧（保存右子树）
3. 把 cur 的左子树移到右侧（调整位置）
4. 左子树置空
5. cur 移到下一个节点继续
|
关键在第 2 步：把右子树挂到 pre.right，相当于给右子树找了个"临时存放点"，这样即使后面 cur.right 被覆盖，右子树也不会丢失
第 3 步：把左子树挂到 cur.right，这样就保证了先序遍历的顺序——当前节点的下一个节点就是左子树的根节点
图解完整过程
以这棵树为例：
1
2
3
4
5
| 1
/ \
2 5
/ \ \
3 4 6
|
当前 cur = 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| 1
/ \
2 5
/ \ \
3 4 6
cur.left = 2（不为空）
左子树为：2 → 3 → 4
最右节点 pre = 4
① pre.right = cur.right（把右子树 5→6 挂到 4 的右侧）
1
/ \
2 5
/ \ \
3 4 6
\
5
\
6
现在节点 4 的右侧接上了 5→6，右子树被"临时存"在了左子树的最右节点下面。注意此时 5 仍然也是 1 的右孩子（引用同一个对象），还没断开
② cur.right = cur.left（左子树 2→3→4 移到右侧）
1
\
2
/ \
3 4
\
5
\
6
③ cur.left = null
1
\
2
/ \
3 4
\
5
\
6
当前 cur 处理完毕，cur 向右移动 → cur = 2
|
关键看第①步做了什么——它把 4 → 5 的指针连上了，这正是先序遍历中左子树最后一个节点（4）到右子树根节点（5）的连接。这保证了右子树不会丢失
当前 cur = 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| 1
\
2
/ \
3 4
\
5
\
6
cur.left = 3（不为空）
左子树为：3
最右节点 pre = 3（3 没有右子树，所以最右就是它自己）
① pre.right = cur.right（把 4→5→6 挂到 3 的右侧）
1
\
2
/ \
3 4
\ \
4 5
\ \
5 6
\
6
现在节点 4 被两个父节点同时引用——既是 2 的右孩子，又是 3 的右孩子。这和第一轮中节点 5 同时被 1 和 4 引用是同样的道理，只是临时状态，等步骤②把左子树挪到右侧后自然就只剩一条链了
② cur.right = cur.left（左子树 3 移到右侧）
1
\
2
\
3
\
4
\
5
\
6
③ cur.left = null
1
\
2
\
3
\
4
\
5
\
6
cur 向右移动 → cur = 3
|
当前 cur = 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| 1
\
2
\
3
\
4
\
5
\
6
cur.left = null，直接跳过
cur 向右移动 → cur = 4
|
当前 cur = 4
1
2
| cur.left = null，直接跳过
cur 向右移动 → cur = 5 → cur = 6 → cur = null
|
循环结束，展开完成
1
2
| 最终结果：
1 → 2 → 3 → 4 → 5 → 6
|
为什么这样做不会丢失节点？
整个过程的核心就一条：找到左子树的最右节点，把右子树挂到它后面
这就像是在玩一个"链条重组"游戏：
- 左子树和右子树原本是并列挂在当前节点左右两侧
- 我们要把链表的顺序变成"当前节点 → 左子树所有节点 → 右子树所有节点"
- 所以需要先把右子树"临时存到"左子树末尾，再把左子树挪到右侧
只要右子树被挂到了左子树最右节点上，它就一定不会丢——因为左子树最右节点是左子树最后一个被访问的节点，访问完它自然会走到右子树
和暴力解法的对比
|
暴力法（先序+List） |
迭代法（原地操作） |
| 额外空间 |
O(n) |
O(1) |
| 遍历次数 |
2遍 |
1遍 |
| 是否需要 TreeNode 存储 |
是 |
否 |
| 理解难度 |
低 |
中 |
迭代法虽然理解起来稍微绕一点，但胜在空间高效，而且只需要一次遍历就能完成展开
复杂度分析
- 时间复杂度：O(n)，每个节点最多作为左子树的"最右节点"被访问一次
- 空间复杂度：O(1)，只用了几个指针变量，没有额外数据结构
