已知二叉树的先序遍历和中序遍历，重构该二叉树

[sunwenli]

• 先序遍历

[1,2,4,7,3,5,6,8]

• 中序遍历

[4,7,2,1,3,5,8,6]

先序遍历规则： 中，左，右
中序遍历规则： 左，中，右

思路
首先，先序数组中下标为 0 的值为根节点，
其次，在中序数组中找到该值，值的左边为根节点的左子树（左子树的中序遍历），值的右边为右子树（右子树的中序遍历）
再次，在先序数组中截出左子树的先序遍历，右子树的先序遍历
最后，左、右子树分别递归上述步骤

javascript解法

function TreeNode(x) {
  this.val = x;
  this.left = null;
  this.right = null;
}

function reconstructorbinarytree(pre, vin) {
  if (pre.length == 0 || vin.length == 0) return null

  let rootNode = pre[0]
  let rdx = vin.indexOf(rootNode)

  let vinleft = vin.slice(0, rdx)
  let vinright = vin.slice(rdx + 1)

  let preleft = pre.slice(1, rdx + 1)
  let preright = pre.slice(rdx + 1)
  return {
    val: rootNode,
    left: reconstructorbinarytree(preleft, vinleft),
    right: reconstructorbinarytree(preright, vinright)
  }
}
// let pre = [1, 2, 4, 7, 3, 5, 6, 8]
// let vin = [4, 7, 2, 1, 3, 5, 8, 6]
// console.log(vin.indexOf(1))
// console.log(pre.slice(1, 3 + 1))
// console.log(pre.slice(4))
let tree = reconstructorbinarytree(pre, vin)
console.log(JSON.stringify(tree))