跳到主要内容

从前序与中序遍历序列构造二叉树

问题​

给定两个整数数组 preorder 和 inorder，其中 preorder 是二叉树的前序遍历，inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例：

输入：preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出：
    3
   / \
  9  20
    /  \
   15   7

来源：LeetCode 105. 从前序与中序遍历序列构造二叉树

前置知识
  • 前序遍历：根 → 左 → 右
  • 中序遍历：左 → 根 → 右
  • 前序的第一个元素一定是根节点
  • 在中序中找到根节点位置，左边是左子树，右边是右子树

答案​

方法一：递归 + HashMap（推荐）​

核心思路：

  1. 前序数组的第一个元素 = 根节点
  2. 在中序数组中找到根节点位置 → 划分左右子树
  3. 根据左子树的节点数量，在前序数组中也划分左右子树
  4. 递归构建
buildTree.ts
class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
  // 用 HashMap 存中序遍历中每个值的索引，避免每次 indexOf 查找
  const inorderMap = new Map<number, number>();
  inorder.forEach((val, idx) => inorderMap.set(val, idx));

  let preorderIdx = 0; // 当前前序遍历的索引

  function build(inLeft: number, inRight: number): TreeNode | null {
    if (inLeft > inRight) return null;

    // 前序遍历的当前元素就是根
    const rootVal = preorder[preorderIdx++];
    const root = new TreeNode(rootVal);

    // 在中序遍历中找到根的位置
    const inorderRootIdx = inorderMap.get(rootVal)!;

    // 先构建左子树（因为前序是 根→左→右）
    root.left = build(inLeft, inorderRootIdx - 1);
    // 再构建右子树
    root.right = build(inorderRootIdx + 1, inRight);

    return root;
  }

  return build(0, inorder.length - 1);
}

图解过程：

preorder = [3, 9, 20, 15, 7]
inorder  = [9, 3, 15, 20, 7]

Step 1: root = 3 (preorder[0])
  中序中 3 的位置是 1
  左子树中序: [9]       右子树中序: [15, 20, 7]
  左子树前序: [9]       右子树前序: [20, 15, 7]

Step 2: 左子树 root = 9,  无左右
Step 3: 右子树 root = 20
  中序中 20 的位置
  左子树中序: [15]      右子树中序: [7]

Step 4: 15 → 叶子
Step 5: 7  → 叶子

结果：
    3
   / \
  9  20
    /  \
   15   7
复杂度分析
  • 时间复杂度：O(n)O(n) — HashMap 查找 O(1)O(1)，每个节点处理一次
  • 空间复杂度：O(n)O(n) — HashMap + 递归栈
没有 HashMap 的话

如果每次用 indexOf 查找根节点位置，时间复杂度退化为 O(n2)O(n^2)。HashMap 是关键优化。

方法二：传递数组范围（不使用全局变量）​

buildTreeRange.ts
function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
  const inorderMap = new Map<number, number>();
  inorder.forEach((val, idx) => inorderMap.set(val, idx));

  function build(
    preStart: number, preEnd: number,
    inStart: number, inEnd: number
  ): TreeNode | null {
    if (preStart > preEnd) return null;

    const rootVal = preorder[preStart];
    const root = new TreeNode(rootVal);
    const inRootIdx = inorderMap.get(rootVal)!;
    const leftSize = inRootIdx - inStart; // 左子树的节点数

    root.left = build(
      preStart + 1, preStart + leftSize,
      inStart, inRootIdx - 1
    );
    root.right = build(
      preStart + leftSize + 1, preEnd,
      inRootIdx + 1, inEnd
    );

    return root;
  }

  return build(0, preorder.length - 1, 0, inorder.length - 1);
}

常见面试追问​

Q1: 从中序与后序遍历序列构造二叉树？(LeetCode 106)​

答案：后序遍历的最后一个元素是根节点，且要先构建右子树再构建左子树：

function buildTree(inorder: number[], postorder: number[]): TreeNode | null {
  const inorderMap = new Map<number, number>();
  inorder.forEach((val, idx) => inorderMap.set(val, idx));

  let postIdx = postorder.length - 1;

  function build(inLeft: number, inRight: number): TreeNode | null {
    if (inLeft > inRight) return null;

    const rootVal = postorder[postIdx--];
    const root = new TreeNode(rootVal);
    const inRootIdx = inorderMap.get(rootVal)!;

    // 注意：后序是「左→右→根」，倒着取是「根→右→左」
    // 所以要先构建右子树！
    root.right = build(inRootIdx + 1, inRight);
    root.left = build(inLeft, inRootIdx - 1);

    return root;
  }

  return build(0, inorder.length - 1);
}

Q2: 只有前序和后序能构造唯一二叉树吗？​

答案：不能。前序 + 后序无法确定唯一的二叉树（当一个节点只有一个子节点时，无法确定是左还是右）。只有前序 + 中序 或 中序 + 后序才能唯一确定。

Q3: 前端中树构建的应用？​

答案：

  • 虚拟 DOM 树构建：从 JSX 编译结果构建 VNode 树
  • AST 构建：Babel 将 tokens 构建成抽象语法树
  • 菜单/路由树：从扁平数据构建嵌套树形结构
// 前端常见：从扁平数组构建树
interface MenuItem {
  id: number;
  parentId: number | null;
  name: string;
  children?: MenuItem[];
}

function buildMenuTree(items: MenuItem[]): MenuItem[] {
  const map = new Map<number, MenuItem>();
  const roots: MenuItem[] = [];

  items.forEach(item => {
    map.set(item.id, { ...item, children: [] });
  });

  items.forEach(item => {
    const node = map.get(item.id)!;
    if (item.parentId === null) {
      roots.push(node);
    } else {
      map.get(item.parentId)?.children?.push(node);
    }
  });

  return roots;
}

相关链接​