手帐 Blog

主题

复盘 · LC 105 从前序与中序遍历序列构造二叉树 ​

题目 ​

题意 ​

给定一棵树的前序与中序遍历（数组），还原唯一的二叉树。

  • 前序：[根, 左子树前序..., 右子树前序...]
  • 中序：[左子树中序..., 根, 右子树中序...]
  • 题目保证元素互不相同，两序列对应同一棵树。

边界：空数组 → null；单节点；左/右子树缺失（根在中序两端）。

涉及算法 ​

标签一句话
分治 / 递归前序定根，中序切左右，再对左右子序列递归
哈希表中序值 → 下标，避免每次线性找根

教程对照：16 · 二叉树遍历（前/中序含义）、17 · 二叉树递归经典（递归返回子树）。

评价我的解法 ​

套路对了：preorder[0] 是根 → 在 inorder 找位置 → slice 出左右两段再递归。能 AC，但实现偏「每次拷贝数组」。

我的代码（摘自 105-从前序与中序遍历序列构造二叉树/index.js，不含本地测例）：

javascript
var buildTree = function (preorder, inorder) {
  const length = preorder.length;
  if (length === 0) {
    return null;
  }
  if (length === 1) {
    return {
      val: preorder[0],
      left: null,
      right: null,
    };
  }
  const root = preorder[0];
  let index = -1;
  for (let i = 0; i < inorder.length; i++) {
    const value = inorder[i];
    if (value === root) {
      index = i;
      break;
    }
  }
  if (index === -1) {
    throw new Error("报错了大哥，访问到-1");
  }
  const inOrderLeftTree = inorder.slice(0, index);
  const inOrderRightTree = inorder.slice(index + 1, inorder.length);
  const preOrderLeftTree = preorder.slice(1, index + 1);
  const preOrderRightTree = preorder.slice(index + 1, preorder.length);
  const left = buildTree(preOrderLeftTree, inOrderLeftTree);
  const right = buildTree(preOrderRightTree, inOrderRightTree);
  const node = {
    val: root,
    left,
    right,
  };
  return node;
};

评价：

  1. 分治边界切对了：左子树长度 = 中序里根左侧元素个数；preorder.slice(1, index + 1) 与中序左段对齐，这是本题核心，写对了。
  2. 每次 slice + 线性找根：每层拷贝子数组、再扫一遍中序，整体偏 O(n²)；内存 132MB、击败约 20% 也符合「拷贝过多」。
  3. length === 1 特判可省：空数组返回 null 后，单节点走通用逻辑即可。
  4. 手写 { val, left, right }：提交能过，面试更稳妥用题目给的 TreeNode。
  5. index === -1 抛错：本地调试有用；LeetCode 保证合法输入，可省略。

小结：思路是标准分治，差在「用下标区间代替拷贝 + Map 定位根」。

最佳题解 ​

中序建 Map，递归只传区间下标，不再 slice：

javascript
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function (preorder, inorder) {
  const indexMap = new Map();
  for (let i = 0; i < inorder.length; i++) {
    indexMap.set(inorder[i], i);
  }

  function build(preL, preR, inL, inR) {
    if (preL > preR) return null;
    const rootVal = preorder[preL];
    const root = new TreeNode(rootVal);
    const inRoot = indexMap.get(rootVal);
    const leftSize = inRoot - inL;
    root.left = build(preL + 1, preL + leftSize, inL, inRoot - 1);
    root.right = build(preL + leftSize + 1, preR, inRoot + 1, inR);
    return root;
  }

  return build(0, preorder.length - 1, 0, inorder.length - 1);
};
  • 时间 O(n)，空间 O(n)（Map + 递归栈）。
  • 为何更优：每个节点只建一次、找根 O(1)；无数组拷贝，复杂度与内存都干净。

关联题目 ​

题为何相关
106. 从中序与后序构造二叉树同一分治，根改取后序末位
889. 根据前序和后序遍历构造二叉树信息更少，切分条件不同
297. 二叉树的序列化与反序列化遍历 ↔ 树 的另一面

一句话带走 ​

前序定根、中序切左右；实现上记住 Map + 下标区间，别每次 slice。