LeetCode 114：二叉树展开为链表（Flatten Binary Tree to Linked List）题解

Flatten Binary Tree to Linked List 是 LeetCode Hot 100 里面一道非常经典的二叉树题。

这道题和普通的“二叉树前序遍历”不太一样。前序遍历更多是在“访问”节点，而这道题要求我们做的事情是：

把整棵二叉树原地改造成一条链表，并且展开顺序必须和前序遍历一致。

这就意味着你不只是要会背：

• 前序遍历是 根 -> 左 -> 右

还要真正理解：

• 当前节点的左子树应该放到哪里

• 原来的右子树又该怎么接回去

• 为什么这样调整之后，最终顺序正好就是前序遍历顺序

你给出的这份 Java 代码，使用的是这道题非常经典的一种写法：

迭代 + 原地重连指针

它不需要额外数组，也不依赖递归，而是直接在原树上完成调整。本文就结合这段代码，系统讲清楚它的思路。

题目介绍

给定一棵二叉树的根节点 root，要求你将它展开为一条“链表”。

这里的“链表”不是新建 ListNode，而是要求：

• 每个节点的 left 都变成 null

• 每个节点的 right 指向链表中的下一个节点

• 最终节点顺序必须和前序遍历一致

例如下面这棵树：

    1
   / \
  2   5
 / \   \
3   4   6

它的前序遍历顺序是：

1 -> 2 -> 3 -> 4 -> 5 -> 6

所以展开之后应该变成：

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

Java 代码

class Solution {
    public void flatten(TreeNode root) {
        TreeNode curr = root;
        while (curr != null) {
            if (curr.left != null) {
                TreeNode next = curr.left;
                TreeNode predecessor = next;
                while (predecessor.right != null) {
                    predecessor = predecessor.right;
                }
                predecessor.right = curr.right;
                curr.left = null;
                curr.right = next;
            }
            curr = curr.right;
        }
    }
}

核心思路

这段代码的核心，可以概括成一句话：

如果当前节点有左子树，就把左子树整体搬到右边，再把原来的右子树接到左子树最右侧节点的后面。

为什么这么做？因为题目要求展开顺序必须是前序遍历，而前序遍历顺序正好是：

根 -> 左 -> 右

所以对于当前节点 `curr“ 来说，调整之后它后面的顺序必须是：

1. 先走左子树

2. 左子树走完之后再走原来的右子树

这就是整个算法的出发点。

代码拆解

1. curr 表示当前处理到的节点

TreeNode curr = root;

因为这份代码是迭代写法，所以我们用 curr 一路向下走。树会被不断改造成只使用 right 指针的链表，因此每次处理完一个节点后，只要继续：

curr = curr.right;

就能进入下一个位置。

2. 为什么只在 curr.left != null 时处理？

if (curr.left != null) {

如果当前节点没有左子树，那么它已经满足题目要求的一部分：左边为空。真正需要处理的，是那些还带着左孩子的节点。

3. next 和 predecessor 分别是什么？

TreeNode next = curr.left;
TreeNode predecessor = next;

• next：当前节点左子树的根

• predecessor：从左子树根出发，一路往右找到的最右节点

为什么要找左子树最右节点？因为我们准备把左子树整体移到右边，但原来的右子树也不能丢。所以必须先找到左子树的“末尾”，把原右子树接上去。

while (predecessor.right != null) {
    predecessor = predecessor.right;
}

这段循环的作用，就是寻找这个“末尾节点”。

4. 三句核心代码到底做了什么？

predecessor.right = curr.right;
curr.left = null;
curr.right = next;

这三句是整道题最关键的部分。

第一句：

predecessor.right = curr.right;

先把原来的右子树接到左子树最右节点后面，避免丢失。

第二句：

curr.left = null;

断开左指针，因为题目要求最终所有节点的 left 都必须为 null。

第三句：

curr.right = next;

把左子树整体移到右边。

这样当前节点附近的顺序就从：

curr -> left / right

变成了：

curr -> left-subtree -> original-right-subtree

而这恰好符合前序遍历“根左右”的顺序。

手动模拟一遍

还是看这棵树：

    1
   / \
  2   5
 / \   \
3   4   6

处理节点 1

• curr = 1

• 左子树根是 2

• 左子树最右节点是 4

执行重连后：

• 4.right = 5

• 1.left = null

• 1.right = 2

结构会变成：

1
 \
  2
 / \
3   4
     \
      5
       \
        6

处理节点 2

• curr = 2

• 左子树根是 3

• 左子树最右节点是 3

执行重连后：

• 3.right = 4

• 2.left = null

• 2.right = 3

此时整棵树就变成：

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

接下来节点 3、4、5、6 都没有左子树，只需要一路向右走即可。

最终得到的顺序就是：

1 -> 2 -> 3 -> 4 -> 5 -> 6

这正好等于原树的前序遍历顺序。

为什么这种方法是正确的？

因为它始终在维护前序遍历的要求：

• 当前节点先出现

• 然后是左子树

• 最后是右子树

如果当前节点没有左子树，那么自然继续向右走就可以。

如果当前节点有左子树，我们就把左子树插到右边，再把原右子树接到左子树末尾。这样每处理完一个节点，它周围的局部顺序就已经被修正为前序遍历顺序。

从根节点开始不断重复这个过程，整棵树最终就会被正确展开。

复杂度分析

时间复杂度

每个节点都会被访问，寻找左子树最右节点会带来一定的重复扫描。通常这种写法在题解中记作：

O(n)

空间复杂度

代码里只用了几个辅助指针，没有使用递归栈和额外数组，所以空间复杂度是：

O(1)

总结

这道题的核心思想可以概括成一句话：

如果当前节点存在左子树，就把左子树整体搬到右边，再把原来的右子树接到左子树最右节点后面；不断重复这个过程，整棵树最终就会按前序遍历顺序展开为链表。

具体步骤就是：

1. 用 curr 指向当前节点

2. 如果当前节点有左子树，记录左子树根 next

3. 找到左子树最右节点 predecessor

4. 让 predecessor.right 接上原右子树

5. 令 curr.left = null

6. 令 curr.right = next

7. 然后继续处理 curr.right

这是一道非常经典的二叉树指针重连题。它真正考察的并不是代码有多长，而是你是否真的理解：

• 前序遍历为什么是“根左右”

• 左子树和右子树在展开后应该如何衔接

• 原地修改树结构时，指针应该按什么顺序调整

把这道题真正吃透之后，再去看 Morris 遍历、二叉树原地改造这类题目时，你会更容易抓住它们背后的共同套路。