[!info] related notes 算法面试题型 MOC 二叉树高频题

Construct Binary Tree from Preorder and Inorder

LeetCode: https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

题目保证两数组来自同一棵树且节点值互不相同。重复值无法用 Map 唯一定位根，任意不一致的两段序列也不保证能构造树；本实现依赖这些前提，不负责校验外部输入。

思路

• 前序遍历：第一个元素一定是当前子树的根。
• 中序遍历：根把序列切成左子树与右子树。
• 用 inorderMap[val] = index 在 O(1) 时间找到根在中序的位置。

递归函数常用参数：

• preStart, preEnd：当前子树在 preorder 的区间
• inStart, inEnd：当前子树在 inorder 的区间

代码（JavaScript）

var buildTree = function(preorder, inorder) {
  const inorderMap = new Map();
  for (let i = 0; i < inorder.length; i++) inorderMap.set(inorder[i], i);

  const build = (preStart, preEnd, inStart, inEnd) => {
    if (preStart > preEnd || inStart > inEnd) return null;

    const rootVal = preorder[preStart];
    const root = new TreeNode(rootVal);
    const rootIndex = inorderMap.get(rootVal);
    const leftSize = rootIndex - inStart;

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

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

区间端点均为闭区间，TreeNode 构造器由题目环境提供。预建 Map 后时间 O(n)，Map 和递归栈额外空间 O(n)；输出树另占 O(n)，不修改输入数组。极深树可能超出 JavaScript 调用栈限制。

Related

• 二叉树高频题