114. 二叉树展开为链表

题目链接（中等）

题目描述

给你二叉树的根结点 root，请你将它展开为一个单链表：

• 展开后的单链表应该同样使用 TreeNode，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null。
• 展开后的单链表应该与二叉树的 先序遍历 顺序相同。

数据范围：树中节点数在范围 [0, 2000] 内，-100 <= Node.val <= 100。

进阶：你可以使用原地算法（$O(1)$ 额外空间）展开这棵树吗？

示例：

输入： root = [1,2,5,3,4,null,6]
输出： [1,null,2,null,3,null,4,null,5,null,6]

核心思路

展开后的链表顺序 = 原二叉树的前序遍历顺序。

所以问题本质上是：把前序遍历的结果，用 right 指针串起来，并把所有 left 置空。

难点在于：直接改结构会破坏树，导致后续无法继续遍历。因此有三种处理方式：

1. 先完整做一次前序遍历，把节点存进列表，再串链表；
2. 边前序遍历边串链表（用栈，先保存子节点信息再改结构）；
3. 原地修改（利用前驱节点，$O(1)$ 空间）。

---

方法一：前序遍历 + 事后串链表

思路及解法

最简单直接：

1. 对二叉树做一次前序遍历，把访问到的节点按顺序存进列表；
2. 遍历列表，把每个节点的 left 置为 None，right 指向下一个节点。

为什么可以这么做？

因为前序遍历先收集完所有节点，此时还没有破坏树结构。等收集完毕，再统一修改指针，就不会丢失信息。

代码

class Solution:
    def flatten(self, root: TreeNode) -> None:
        nodes = []

        def preorder(node):
            if not node:
                return
            nodes.append(node)
            preorder(node.left)
            preorder(node.right)

        preorder(root)

        for i in range(1, len(nodes)):
            prev, curr = nodes[i - 1], nodes[i]
            prev.left = None
            prev.right = curr

复杂度分析

• 时间复杂度：$O(n)$，前序遍历一次，串链表一次。
• 空间复杂度：$O(n)$，nodes 列表存了所有节点，递归栈深度最坏为 $O(n)$。

---

方法二：边遍历边展开（栈模拟）

思路及解法

方法一需要先收集全部节点，再串链表。能不能一边前序遍历一边串链表？

可以，但要注意：在修改当前节点的指针之前，必须先把它左右孩子的信息保存下来，否则修改后就找不到了。

做法：

• 用栈模拟前序遍历；
• 每次从栈中弹出当前节点 curr；
• 把 prev.right = curr、prev.left = None（若 prev 非空）；
• 先右后左入栈（因为栈是后进先出，这样出栈顺序才是「先左后右」）；
• 更新 prev = curr。

为什么不能递归？

递归是「访问完当前节点再深入」，此时还没保存子节点，指针就改乱了。迭代可以在修改之前先把左右孩子压栈，信息不会丢。

代码

class Solution:
    def flatten(self, root: TreeNode) -> None:
        if not root:
            return

        stack = [root]
        prev = None

        while stack:
            curr = stack.pop()

            # 串链表
            if prev:
                prev.left = None
                prev.right = curr

            # 先压右再压左，保证出栈是左、右
            if curr.right:
                stack.append(curr.right)
            if curr.left:
                stack.append(curr.left)

            prev = curr

复杂度分析

• 时间复杂度：$O(n)$，每个节点访问一次。
• 空间复杂度：$O(n)$，栈的深度最坏为 $O(n)$（链状树）。

---

方法三：原地展开（找前驱节点）

思路及解法

目标：不用栈、不用额外数组，$O(1)$ 空间完成。

关键观察：前序顺序是「根 → 左子树 → 右子树」。

假设当前节点 curr 有左子树，那么：

• curr 的前序遍历中，左子树中最右的节点（也就是左子树前序里最后被访问的那个），是 curr 的前驱节点；
• 前序遍历的下一个节点，正是 curr 左子树的根（curr.left）。

因此可以这样操作：

1. 找到 curr.left 子树中的最右节点 predecessor；
2. 把 curr.right 接到 predecessor.right；
3. 把 curr.left 移到 curr.right，并把 curr.left 置空；
4. 令 curr = curr.right，继续处理。

为什么最右节点就是前驱？

因为前序遍历会先把左子树全部访问完（顺序是「左 → 左左 → … → 左子树的最右」），然后才访问右子树。所以左子树的最右节点，恰好是右子树之前被访问的最后一个节点。

关键性质：每次处理完 curr 后，curr.right 一定指向下一个该访问的节点（要么是原来的左子树根，要么是原来的右子树根）。因此只需一路沿着 right 走到底即可。

代码

class Solution:
    def flatten(self, root: TreeNode) -> None:
        curr = root
        while curr:
            if curr.left:
                # 找到左子树的最右节点（前驱节点）
                predecessor = curr.left
                while predecessor.right:
                    predecessor = predecessor.right

                # 前驱的 right 接上原 curr.right
                predecessor.right = curr.right
                # 把左子树移到右子树位置
                curr.right = curr.left
                curr.left = None

            # 沿 right 继续处理下一个节点
            curr = curr.right

复杂度分析

• 时间复杂度：$O(n)$，每个节点只被访问一次，寻找前驱时每个节点最多额外被访问一次。
• 空间复杂度：$O(1)$，原地修改，不用任何额外结构。

---

三种方法对比

方法	时间	空间	是否原地	特点
一：先序遍历 + 事后串	$O(n)$	$O(n)$	否	思路最直白
二：边遍历边串（栈）	$O(n)$	$O(n)$	否	迭代实现，稍微巧妙
三：找前驱节点	$O(n)$	$O(1)$	是	满足进阶要求，最优雅

推荐：

• 面试开场：方法一，最容易讲清楚前序顺序和改指针的关系；
• 追问优化：方法三，展示对前序遍历结构的深入理解，也是本题的「进阶答案」；
• 日常刷题：方法三代码最短，也最高效。

总结

• 本质：把前序遍历的结果用 right 串起来，left 全置空；
• 难点：修改结构会丢失子树信息，需要先保存、后修改；
• 方法一：前序收集全部节点 → 再串链表，思路直接；
• 方法二：迭代 + 栈，修改前先把左右孩子压栈；
• 方法三：原地法，核心是「找到左子树的最右节点（前驱），把右子树接到它后面」；
• 记住这句话：前序 = 根 → 左子树 → 右子树，所以左子树的最右节点是右子树的「前一个」。