跳到主要内容

LeetCode 114. 二叉树展开为链表

本节目标

按右、左、根的逆前序递归，用前驱节点在线性时间内原地重连右链。

这是路径状态与结构变换中最典型的原地重连题。要把树改成只使用 right 指针的链表，节点顺序必须等于原树的前序遍历，且每个 left 指针都必须为空。

查看 LeetCode 原题

题意与关键边界​

原有节点必须全部保留，不能新建一串只含相同值的节点。空树无需操作；单节点保持原状。完成后从根沿 right 前进应恰好经过原树的每一个节点一次，既不能丢节点，也不能形成环。

朴素思路与瓶颈​

一种直接做法是在每个节点把左子树接到右边，并不断寻找左子树展开后链表的最右端再接回旧右子树。它在偏斜形状下会反复扫描尾部，最坏达到 O(n²)，不适合作为主解法。

更稳妥的思路是反过来构造前序链表：若已经知道“当前节点在前序中的下一个节点”，只需把它接到当前节点右边即可。

逆前序前驱不变量​

前序顺序是根—左—右，倒过来就是右—左—根。设 previous 始终指向已经处理好的前序后继链的头部。

处理一个节点时，先递归右子树，再递归左子树。这样轮到当前节点时，原前序中应排在它之后的左子树链已经接在 previous 前面，右子树链也已经作为那条链的后部；令 node.right = previous 就得到正确后继，再清空 node.left 并把 previous 更新为当前节点。

入口每次调用都把 previous 重置为空。否则复用同一个 Solution 实例处理第二棵树时，会把前一次的链错误地接到新树尾部。

正确性依据​

按右—左—根的处理顺序归纳。空节点不改变 previous。处理某节点前，右子树和左子树都已按原前序各自展开，且 previous 指向“左子树链在前、右子树链在后”的前序后继链。把当前节点右指针指向 previous，正好把当前根放到该拼接前；清空左指针后，得到以当前节点开头的完整前序右链。每个节点只被重连一次，节点集合不变。

代码实现​

C++17
class Solution {
private:
    TreeNode* previous;

    void flattenDfs(TreeNode* node) {
        if (node == nullptr) {
            return;
        }

        flattenDfs(node->right);
        flattenDfs(node->left);
        node->right = previous;
        node->left = nullptr;
        previous = node;
    }

public:
    void flatten(TreeNode* root) {
        previous = nullptr;
        flattenDfs(root);
    }
};

C++ 把前驱保存为成员指针，Python 保存为实例字段；两份入口都在开始 DFS 前重置它。测试会检查右链值序、所有左指针、节点数量和环，因此不仅验证表面顺序。

复杂度分析​

每个节点恰好递归、重连一次，时间复杂度为 O(n)。除递归调用栈外不使用与节点数同级的辅助容器，额外空间为 O(h)；最坏退化树为 O(n)。

边界与易错点​

  • 递归顺序写成左—右—根会得到错误的后继关系。
  • 忘记 node.left = null / None，最终结构不是题目要求的链表。
  • 未在入口重置前驱，重复调用同一实例会把两棵树串在一起。
  • 覆盖右指针前没有处理或保存原右子树，会丢失尚未访问的节点。
  • 只比较链上几个值不足以发现环或节点丢失，应同时检查长度和节点身份。

模式迁移​

需要按后序或中序重连时，先写出目标顺序的反向顺序，再决定 previous 应代表什么。若递归深度可能超过语言栈限制，可用显式栈按前序访问，并维护上一访问节点完成相同的重连。