106.从中序与后序遍历序列构造二叉树

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

给定两个整数数组 inorder 和 postorder，其中 inorder 是二叉树的中序遍历，postorder 是同一棵树的后序遍历，请你构造并返回这颗二叉树。

解析

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