vvrf / DSA.log

问题拆解

把二叉树原地展开成一条只用 right 指针串起来的“链表”，节点顺序必须等于先序遍历。

最直白的做法是先做一遍先序遍历把节点存进列表，再依次重接指针——正确，但 O(n) 额外空间，而且“原地”的意味就没了。想不开辅助数组，就得在遍历的同时完成重接。

递归的分解方式很自然：假设左、右子树已经各自展开成链（这正是递归能提供的），根节点要做的只是接线——先序顺序是“根 → 左 → 右”，所以把展开后的左链搬到 root.right，原来的右链接到左链的末端，最后记得把 root.left 置空。难点只剩一个：找左链的末端，即一路向 right 走到底的那个节点。

后序处理的价值：等左右子树都变成“已展开的链”之后再动手，根节点面对的就不再是一棵树，而是两条头尾分明的链——接线成了纯粹的指针操作。

递归后序展开再接线

public void flatten(TreeNode root) {
    if (root == null) {
        return;
    }
    flatten(root.left);
    flatten(root.right); // 左右子树先各自成链
    TreeNode left = root.left;
    if (left != null) {
        TreeNode tail = left;
        while (tail.right != null) {
            tail = tail.right; // 找左链末端
        }
        tail.right = root.right; // 原右链接到左链末尾
        root.right = left;
        root.left = null; // 别忘了断开 left
    }
}

def flatten(root: Optional[TreeNode]) -> None:
    if not root:
        return
    flatten(root.left)
    flatten(root.right)  # 左右子树先各自成链

    if root.left:
        tail = root.left
        while tail.right:
            tail = tail.right  # 找左链末端
        tail.right = root.right  # 原右链接到左链末尾
        root.right = root.left
        root.left = None  # 别忘了断开 left

func flatten(root *TreeNode) {
    if root == nil {
        return
    }
    flatten(root.Left)
    flatten(root.Right) // 左右子树先各自成链
    if root.Left != nil {
        tail := root.Left
        for tail.Right != nil {
            tail = tail.Right // 找左链末端
        }
        tail.Right = root.Right // 原右链接到左链末尾
        root.Right = root.Left
        root.Left = nil // 别忘了断开 left
    }
}

pub fn flatten(root: &mut Option<Rc<RefCell<TreeNode>>>) {
    if let Some(node) = root {
        // 先取下左右子树，避免与后续 borrow_mut 冲突
        let mut left = node.borrow_mut().left.take();
        let mut right = node.borrow_mut().right.take();
        Self::flatten(&mut left);
        Self::flatten(&mut right); // 左右子树先各自成链
        if left.is_some() {
            // 找左链末端
            let mut tail = Rc::clone(left.as_ref().unwrap());
            loop {
                let next = tail.borrow().right.clone();
                match next {
                    Some(n) => tail = n,
                    None => break,
                }
            }
            tail.borrow_mut().right = right; // 原右链接到左链末尾
            node.borrow_mut().right = left;
        } else {
            node.borrow_mut().right = right;
        }
    }
}

最容易忘的一步是 root.left = null：指针都接对了，但左指针没断开，遍历结果看似正确，判题时按“left 必须全为空”检查就会挂掉。Rust 版还有一处值得注意：先用 take() 把左右子树从节点上摘下来再递归，这样后面 borrow_mut() 接线时就不会和活着的借用冲突；找末端时也不能一直握着 borrow() 往下走，要先 clone 出下一个 Rc 再释放当前借用，否则借用生命周期叠在一起直接编不过。

顺带一提，这题还有个精巧的 O(1) 空间迭代解（对每个有左子树的节点，找到左子树最右节点做“前驱”，把右链挂过去），思想同 Morris 遍历；递归版胜在思路直白，面试先写它不亏。

复杂度

指标	复杂度	原因
时间	`O(n)`	每个节点被递归访问一次；找末端沿的都是不重复的 right 边，总步数 O(n)
空间	`O(h)`	递归栈深度为树高，最坏退化成 O(n)

可以迁移的模式

改树形结构的题优先考虑后序：子树先处理完，根节点面对的是结构已知的成品；
“把一段插入另一段”类指针操作，先找清楚四个关键点：插入段的头尾、断口的前后；
Rust 树题的通用手法：take() 先摘子树、Rc::clone 传递所有权、缩短每次 borrow 的存活范围。

递归定义即接口契约——相信“子调用返回时子树已经是链”，根节点的逻辑就只剩三行指针。