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

例如，给出

中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]

返回如下的二叉树：

3
   / \
  9  20
    /  \
   15   7

/**
 * @param {number[]} inorder
 * @param {number[]} postorder
 * @return {TreeNode}
 */
var buildTree = function(inorder, postorder) {
  return build(0, inorder.length - 1, 0, postorder.length - 1);
  function build(inStart, inEnd, postStart, postEnd) {
    if (postStart > postEnd) {
      return null;
    }
    // 根节点为后序遍历最后一个节点
    const rootValue = postorder[postEnd];
    let index = 0;
    for (let i = inStart; i <= inEnd; i++) {
      if (rootValue === inorder[i]) {
        index = i;
        break;
      }
    }
    // 左子树个数
    const leftSize = index -  inStart;
    const root = new TreeNode(rootValue);
    // 左子树 中序遍历数组起点为inStart， 终点为index - 1 后序遍历起点为postStart，终点为postStart + leftSize - 1
    root.left = build(inStart, index - 1, postStart, postStart + leftSize - 1);
    // 右子树 中序遍历数组起点为index + 1， 终点为inEnd 后序遍历起点为postStart + leftSize - 1 + 1,终点为postEnd - 1（postend为根节点）
    root.right = build(index + 1, inEnd,postStart + leftSize, postEnd - 1);
    return root;
  }
};