题解 | #40.重建二叉树#

递归

根据二叉树的前序遍历，前序遍历的第一个元素一定是根节点，从中序数组找到这个元素，将中序数组划分位2部分，根节点左侧是左子树，根节点右侧是右子树，继续递归即可

step1：根据前序遍历第一个结点建立根节点

step2：在中序遍历中找到根节点在数组的位置

step3：根据根节点将中序数组划分位两个数字，分别为左子树轭函右子树

step4：子树的序列长度为0，结束递归，返回null

function reConstructBinaryTree(pre, vin)
{
  if(pre.length==0 || vin.length==0)
    return null;
  
  let root = new TreeNode(pre[0]);
  let rootIndexInVin = vin.indexOf(pre[0]);//找到root在中序数组的位置
  
  root.left = reConstructBinaryTree(pre.slice(1,rootIndexInVin+1),vin.slice(0,rootIndexInVin));
  root.right = reConstructBinaryTree(pre.slice(rootIndexInVin+1,pre.length),vin.slice(rootIndexInVin+1,vin.length));
  
  return root;
}