LC114　二叉树展开为链表¶

中等通过率 76.2%python3核心代码模式二叉树样例通过牛客 AC栈树深度优先搜索链表二叉树

一句话

把左子树整段插到右子树前面，逐个节点原地重挂指针。

解题思路¶

这题考什么¶

要求原地把树改成一条只用 right 指针串起来的链，顺序是前序（根、左、右），进阶还要求 O(1) 额外空间。

「先前序遍历一遍拿到序列，再回头重挂」当然可行，但那要存下整个序列，空间 O(n)。 O(1) 的做法来自一个局部观察：对任意节点 cur，展开后紧跟在 cur 后面的，一定是它左子树的第一个节点；而左子树展开后的最后一个节点，后面接的必然是 cur 原来的右子树。左子树在前序里的最后一个节点，就是它的「最右链末端」—— 从 cur.left 出发一路沿 right 走到头。

于是每个节点只做一次固定的手术：

cur 有左子树时：
    pred = 从 cur.left 一路沿 right 走到头（左子树前序的最后一个节点）
    pred.right = cur.right   把原来的右子树接到左子树的尾巴上
    cur.right = cur.left     左子树整段提到右边
    cur.left = None          题目要求 left 一律置空
然后 cur = cur.right，继续处理新的右链。

这样一路推进，走到底时整棵树就成了一条右链，顺序恰是前序。这套「找前驱、借它的空指针」的手法与 Morris 遍历同源，树上算法的这类技巧见树的基础与遍历。

示例 1 的 [1,2,5,3,4,null,6]：

cur = 1，左子树是 (2,3,4)，它的最右链末端是 4；
         于是 4.right = 5，1.right = 2，1.left = None
cur = 2，左子树是 (3)，末端是 3；3.right = 4，2.right = 3，2.left = None
cur = 3、4、5、6 都没有左子树，一路直走

结果是 1 -> 2 -> 3 -> 4 -> 5 -> 6，与样例一致。

数据规模与复杂度¶

节点数在 [0, 2000]，节点值在 [-100, 100]。外层沿右链走 O(n) 步；内层找前驱走过的每条边最多被走两次（一次是前驱查找、一次是外层前进），总时间 O(n)。额外空间只有 cur、pred 两个指针，O(1)，满足进阶要求。全程没有递归，2000 个节点排成一条链也不涉及栈深度问题。

坑在哪¶

三步重挂有严格顺序：先把原来的 cur.right 接到前驱后面，再把左子树提上来。顺序反了（先写 cur.right = cur.left）原来的右子树就丢了引用，再也找不回来。
cur.left 必须置成 None。题目明确要求展开后左指针全为空；不置空的话树里还留着旧的左边，序列化出来根本不是一条链。
返回值是 None，答案留在入参里。这是原地修改题，声明的返回类型就是 void，判题时回头读第 0 个参数（root）看结果。写 return root 不会被采纳。
空树要能安全通过。root 为 None 时 while 一次都不进，函数直接结束；题面示例 2 给的正是空树。
没有左子树时什么都不做，直接前进。此时右子树已经在它该在的位置上，多余的操作只会把已经排好的链搅乱。

参考实现¶

solutions/leetcode/LC114/sol.py
from typing import List, Optional


class Solution:
    def flatten(self, root: "Optional[TreeNode]") -> None:
        # cur 沿着「已经展开好的右链」向下推进；root 为 None 时循环一次都不进
        cur = root
        while cur is not None:
            # 没有左子树就无事可做，右子树本来就在该在的位置上
            if cur.left is not None:
                # 前驱 = 左子树在前序里的最后一个节点 = 左子树最右链的末端
                pred = cur.left
                while pred.right is not None:
                    pred = pred.right
                # 三步的先后不能换：先把原右子树接到前驱后面，再提左子树，
                # 反过来写会先覆盖 cur.right，原来的右子树就丢了引用
                pred.right = cur.right
                cur.right = cur.left
                # 题目要求展开后所有 left 都是空
                cur.left = None
            # 前进到新的右孩子：它要么是刚提上来的左子树的头，要么是原来的右子树
            cur = cur.right

LC114 二叉树展开为链表¶