如何把二叉树原地展开为链表？

简化版

把二叉树展开为链表通常要求按前序遍历顺序，把所有节点通过 right 指针串起来，left 置空。可以后序递归先展开左右子树，再把左链接到右侧、原右子树接到左链尾部；时间 O(n)，空间 O(h)。

详细版

对每个节点，先递归展开左子树和右子树。然后保存原右子树，把展开后的左子树放到 root.right，将 root.left 置空，再找到新右链尾部，把原右子树接上。

void flatten(TreeNode root) {
    if (root == null) return;
    flatten(root.left);
    flatten(root.right);
    TreeNode left = root.left;
    TreeNode right = root.right;
    root.left = null;
    root.right = left;
    TreeNode p = root;
    while (p.right != null) p = p.right;
    p.right = right;
}

这版容易理解，但每层找尾部可能导致最坏 O(n²)。优化写法可以反向前序：按右、左、根递归，用 prev 指向已经处理好的链表头。

完整版教学

一、展开后的顺序是前序遍历顺序

题目不是随便把节点串成链表，而是要求顺序等于前序遍历：根、左、右。展开后所有节点的 left 都要为 null，right 指向下一个前序节点。理解这个目标后，很多操作就变成了“把左子树整体插到根和右子树之间”。

原树前序: 1,2,3,4,5,6
展开后:
1 -> 2 -> 3 -> 4 -> 5 -> 6

因为前序先访问左子树，所以原左子树必须排在原右子树前面。不能简单地把左右子树分别展开后保持原位置不动。

二、局部重接线的过程

假设当前节点的左右子树都已经展开成链。当前节点要做三件事：保存原右链，把左链移动到右边，把原右链接到新右链尾部。这个过程只改指针，不创建新节点，所以满足原地要求。

root
├─ leftChain:  L1 -> L2
└─ rightChain: R1 -> R2

变成:
root -> L1 -> L2 -> R1 -> R2

这就是为什么递归处理顺序通常写成后序：先保证左右子树已经各自展开，再在当前节点处做合并。

三、朴素递归为什么可能 O(n²)

朴素写法每个节点都要沿着新右链找到尾部。如果树退化成一条左链，第一个节点找尾部走 n 步，第二个走 n-1 步，累计接近 n(n-1)/2。这会让本来应该 O(n) 的题变慢。

n=5 左链:
找尾步数约 4 + 3 + 2 + 1 = 10
n 节点约 n(n-1)/2

所以面试时可以先讲易懂版，再补充优化版。这样既能说明思路，也能体现复杂度意识。

四、反向前序如何做到 O(n)

前序是根、左、右；如果反过来处理，就是右、左、根。维护一个 prev 指针，表示已经展开好的后续链表头。访问当前节点时，把 current.right = prev，current.left = null，再令 prev = current。每个节点只处理一次，不需要找尾部。

TreeNode prev = null;

void flatten(TreeNode root) {
    if (root == null) return;
    flatten(root.right);
    flatten(root.left);
    root.right = prev;
    root.left = null;
    prev = root;
}

这个写法的难点是方向反直觉，但它实际是在从链表尾部往头部构造。

五、迭代写法也能原地完成

还可以用类似 Morris 的思想：对每个有左子树的节点，找到左子树最右节点，把当前右子树接到它后面，再把左子树整体挪到右边。然后当前指针沿 right 往下走。这个写法不需要递归栈，额外空间 O(1)。

写法	时间	额外空间	特点
朴素递归找尾	最坏 O(n²)	O(h)	好理解
反向前序递归	O(n)	O(h)	代码短
迭代原地重接	O(n)	O(1)	指针操作多

如果面试官强调“原地且 O(1) 额外空间”，就要说迭代重接线版本。

六、常见误区与追问

易错点：展开不是新建链表，而是复用原节点，把 left 清空、right 串成前序顺序。

误区：按中序或层序展开也可以。 题目要求通常是前序，顺序错了即使链表形态对也不合格。
误区：可以创建新节点。 原地展开要求复用原节点，创建新链表不符合题意。
误区：忘记把 left 置空。 展开后的结构要求所有左指针为空，否则仍不是链表。
追问：朴素写法为什么可能 O(n²)？ 每层找尾部会重复走已经展开过的链。
追问：如何做到 O(1) 额外空间？ 用迭代重接线，找到左子树最右节点并拼接原右子树。
追问：反向前序里的 prev 是什么？ 它是当前节点之后已经展开好的链表头。

七、加强记忆

这题的核心画面是“把左链塞到根和右链之间”。前序顺序决定左子树必须排在右子树前，原地要求决定只能改左右指针。易懂版先展开左右再拼接，优化版用右、左、根的反向前序从尾到头接链；记住这两个视角，面试中既能写出代码，也能解释复杂度。

简化版

详细版