71.重建二叉树

day18: 剑指 Offer 07. 重建二叉树（中等）
思路：前序遍历：根左右，可以判定第一个节点一定是根节点。
后序遍历：左根右,可以判定左节点和右节点中间的一定是根节点。
因此在每次截取到的左树和右树中可以判断每一个子树的根节点和左右节点，以此类推，递归即可。

//判断右左节点和右节点是否存在
var buildTree = function (pre, vin) {
  if (pre.length === 0 || vin.length === 0) {
    return null;
  }

  var index = vin.indexOf(pre[0]); //找到根节点

  var left = vin.slice(0, index); //左子树的中序序列
  var right = vin.slice(index + 1); //右子树的中序遍历
  var node = new TreeNode(pre[0]);
  node.left = buildTree(pre.slice(1, index + 1), left);
  node.right = buildTree(pre.slice(index + 1), right);
  return node;
};

2022年7月6日更新
根据先序和后序不能唯一确定一棵二叉树；
根据先序和中序或者中序和后序可以唯一确定一棵二叉树。
总结：

• 找到根节点
• 根据根节点位置划分左右区间，找到划分区间的位置
• 找好左右的区间，然后递归遍历左子树和右子树。