手帐 Blog

主题

复盘 · LC 114 二叉树展开为链表 ​

题目 ​

题意 ​

把二叉树原地展开成一条「链表」：

  • 展开后所有节点 left === null，right 指向前序遍历的下一个节点。
  • 题目要求 void：改根节点指向的那棵树，不另返回新根。

边界：空树；单节点；只有左子树 / 只有右子树。

涉及算法 ​

标签一句话
前序展开顺序必须是「根 → 左子树前序 → 右子树前序」
递归返回尾先展平左右，再把左链接到根右、右链接到左尾
找前驱（Morris 味）把左子树接到右子树前，左子树最右连到原右

教程对照：16 · 二叉树遍历、12 · 链表基础（指针改接）。

评价我的解法 ​

你用「递归展平 + 返回子链尾巴」把左右接起来，本地与提交都过了（0ms），方向正确。

我的代码（摘自 114-二叉树展开为链表/index.js，不含本地测例）：

javascript
var flatten = function (root) {
  if (!root) {
    return null;
  }
  if (!root.left && !root.right) {
    root.left = null;
    root.right = null;
    return root;
  }
  if (!root.left) {
    let right = root.right;
    const rightFail = flatten(right);
    root.left = null;
    return rightFail;
  }
  if (!root.right) {
    let left = root.left;
    const leftFail = flatten(left);
    root.left = null;
    root.right = left;
    return leftFail;
  }
  if (root.left && root.right) {
    let left = root.left;
    let right = root.right;
    root.left = null;
    const leftFail = flatten(left);
    const rightFail = flatten(right);
    root.right = left;
    if (leftFail) {
      leftFail.right = right;
    } else if (rightFail) {
      root.right = right;
    }
    return rightFail;
  }
};

评价：

  1. 契约对了：函数既改树，又返回「展开后链尾」，方便上层拼接——这是正确的递归设计。
  2. 四分支过碎：无左 / 无右 / 左右都有拆开写，读起来累；其实可统一成「先展左右 → 根接左链 → 左尾接右链 → 返回整段尾」。
  3. 命名 leftFail / rightFail：实际是 tail，面试口述会自己绕晕；应叫 leftTail / rightTail。
  4. else if (rightFail) 基本走不到：left 非空时展平后 leftFail 应为非空；死分支说明分支推演还不干净。
  5. 复杂度：时间 O(n)、栈 O(h)，作为解法没问题；题目说 void，返回值仅作内部约定即可（提交不看返回）。

小结：能 AC 且快；下一刀是把四段合并成「返回尾巴」的干净模板，并改掉命名。

最佳题解 ​

推荐两种口述友好写法。

写法 A · 递归返回尾（把你今天的思路收成一版）：

javascript
/**
 * @param {TreeNode} root
 * @return {void}
 */
var flatten = function (root) {
  function dfs(node) {
    if (!node) return null;
    if (!node.left && !node.right) return node;

    const left = node.left;
    const right = node.right;
    const leftTail = dfs(left);
    const rightTail = dfs(right);

    if (left) {
      node.left = null;
      node.right = left;
      leftTail.right = right;
    }
    return rightTail || leftTail || node;
  }
  dfs(root);
};

写法 B · 倒序前序（右 → 左 → 根，边走边接）：

javascript
var flatten = function (root) {
  let prev = null;
  function dfs(node) {
    if (!node) return;
    dfs(node.right);
    dfs(node.left);
    node.right = prev;
    node.left = null;
    prev = node;
  }
  dfs(root);
};
  • 时间 O(n)，空间 O(h)（递归栈）。
  • 为何更优：分支少、无死代码；B 版口述「从后往前串」也很好记。进阶还可讲 O(1) 额外空间的前驱穿线写法。

关联题目 ​

题为何相关
144. 二叉树的前序遍历展开顺序就是前序
430. 扁平化多级双向链表同样「子结构插入再接回」
116. 填充每个节点的下一个右侧节点指针也是改指针串节点，不改值

一句话带走 ​

展开成前序链表：递归时返回子链尾巴，根接左、左尾接右；或倒序前序边走边挂 right。