二叉树展开为链表 图解题解

题目要求的链表长什么样

题目要求把二叉树原地改造成一条只用右指针串起来的单链表：每个节点的 left 都置空，right 指向它在先序遍历（根、左、右）中的下一个节点。题目同时提出两个要求：节点顺序必须严格等于先序，并且要在原来这棵树上直接改指针，不另外新建结构。

先存先序序列再重接，代价在哪里

最直接的做法是先做一遍先序遍历，把节点按顺序存进列表，再从头到尾把 right 逐个接上、left 置空。它正确且好写，但要 O(n) 的额外空间存整个序列；改成递归原地拼接可以省掉列表，递归栈仍要 O(h)。想做到真正的 O(1) 额外空间，就得在不记录任何全局顺序的前提下，靠局部的指针操作一段一段地把树拉直。

关键观察：原右子树该临时接到哪里

回到先序的定义，考察任意一个节点 cur：cur 之后紧跟的是它的整棵左子树，左子树全部走完才轮到原来的右子树。所以把左子树搬到右边之前，必须先给原右子树找一个不破坏顺序的落脚点。做法是沿左子树的右指针一路走到底，找到当前右链的末端节点，把原右子树接到它后面。注意这个末端节点不一定是左子树先序的最后一个节点——左子树里可能还有没展开的左分支——但挂在这里不会出错：先序先左后右，挂上去的整段仍然排在左子树现有全部节点之后；等 cur 往下走到那些更深的左分支时，同样的操作会把这段继续往下推，最终恰好落到完整先序的正确位置。这个「沿右链找接驳点」的手法与 Morris 遍历找前驱是同款技巧。

每一步搬运为什么不丢节点、拼出来恰好是先序

对每个有左子树的节点做三个动作，次序不能乱：先让右链末端节点接管原右子树——先把右子树托付出去，它才不会在下一步被覆盖丢失；再把整棵左子树搬到 right 上；最后把 left 置空。这一轮结束时保证的是三件事：原右子树完好挂在树里没有脱链、左子树整体挪到了 cur 的右侧、cur 本身满足「左空右连」的链表形态——完整的先序顺序并不靠这一轮一次做完，而是 cur 沿 right 前进后，对后面每个还有左子树的节点重复同样的操作，一段一段逐步成形。

两个高频错误：先搬左子树再想起原右子树，此时右指针已被覆盖、整棵右子树永久丢失；搬完忘记把 cur.left 置空，结果不满足「只有右孩子」的链表形态。

为什么总时间还是线性 O(n)

看起来「找最右节点」像嵌套循环，其实不然：每个节点作为某次寻找前驱的途经点，总共只会被走过常数次，所有寻找加起来的步数是线性的，时间 O(n)。空间上只用 cur、pre 两个指针，既无递归也无栈，额外空间 O(1)——这正是它比「先序列表重接」和递归拼接更进一步的地方。

Java

class Solution {
    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;                    // 沿右脊前进
        }
    }
}

Python

class Solution:
    def flatten(self, root: TreeNode) -> None:
        cur = root
        while cur:
            if cur.left:
                pre = cur.left                  # 左子树
                while pre.right:                # 找左子树最右(先序末尾)
                    pre = pre.right
                pre.right = cur.right           # 原右子树接到它后面
                cur.right = cur.left            # 左子树整段搬到右边
                cur.left = None                 # 左指针清空
            cur = cur.right                     # 沿右脊前进

C++

class Solution {
public:
    void flatten(TreeNode* root) {
        TreeNode* cur = root;
        while (cur != nullptr) {
            if (cur->left != nullptr) {
                TreeNode* pre = cur->left;      // 左子树
                while (pre->right != nullptr)   // 找左子树最右(先序末尾)
                    pre = pre->right;
                pre->right = cur->right;        // 原右子树接到它后面
                cur->right = cur->left;         // 左子树整段搬到右边
                cur->left = nullptr;            // 左指针清空
            }
            cur = cur->right;                   // 沿右脊前进
        }
    }
};