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

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

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

解析

var buildTree = function (preorder, inorder) {
  const map = new Map();
  inorder.forEach((val, idx) => map.set(val, idx));
  let preIdx = 0;
  function build(lo, hi) {
    if (lo > hi) return null;
    const rootVal = preorder[preIdx++];
    const root = new TreeNode(rootVal);
    const mid = map.get(rootVal);
    root.left = build(lo, mid - 1);
    root.right = build(mid + 1, hi);
    return root;
  }
  return build(0, inorder.length - 1);
};