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

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

        3
   / \
  9  20
    /  \
   15   7

 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function(preorder, inorder) {
  return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1)
};

function build(preorder, preStart, preEnd, inorder, inStart, inEnd) {
  if (preStart > preEnd) {
    return null;
  }
  // 前序遍历 第一个为根节点
  const rootValue = preorder[preStart];
  let index = 0;
  // 寻找根节点在中序遍历的位置
  for (let i = inStart; i <= inEnd; i++) {
    if (inorder[i] === rootValue) {
      index =i;
      break;
    }
  }

  const leftSize = index - inStart;
  // 构造根节点
  const root = new TreeNode(rootValue);
  // 左子树的前序遍历起点为preStart + 1，终点为preStart + leftSize 中序遍历起点为inStart， 终点为index - 1
  root.left = build(preorder, preStart + 1, preStart + leftSize, inorder, inStart, index - 1)
  // 右子树的前序遍历起点为preStart + leftSize + 1，终点为preEnd 中序遍历起点为index + 1， inEnd
  root.right = build(preorder, preStart + leftSize + 1, preEnd, inorder, index + 1, inEnd);
  return root;
}