每日一题 [8]-重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

解：
二叉树的一般结构：

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

二叉树的前序遍历：

function PreOrderTraverse(treeNode)  
{  
    if(treeNode.val== NULL)  
        return;  
    Visit(treeNode); // 访问根节点  
    PreOrderTraverse(treeNode.left); // 前序遍历左子树  
    PreOrderTraverse(treeNode.right); // 前序遍历右子树  
}  

二叉树的中序遍历：

function InOrderTraverse(treeNode)  
{  
    if(treeNode.val== NULL)  
        return;  
    InOrderTraverse(treeNode.left); // 中序遍历左子树  
    Visit(treeNode.val); // 访问根节点  
    InOrderTraverse(treeNode.right); // 中序遍历右子树  
}  

二叉树的后序遍历：

void PostOrderTraverse(treeNode)  
{  
    if(pRoot == NULL)  
        return;  
    PostOrderTraverse(treeNode.left); // 后序遍历左子树  
    PostOrderTraverse(treeNode.right); // 后序遍历右子树  
    Visit(treeNode.val); // 访问根节点  
}  

了解到二叉树的遍历常用递归后，这道题应该也是用的递归。完美的逻辑o(￣▽￣)ブ。
这道题的思路是，通过前序遍历序列找出根节点，再通过中序遍历序列找出左右节点。
解题思路很简单，但是结果的输出需要分层遍历ヽ(*。>Д<)o゜
∑( 口 ||，参考了别人的代码才知道，原来返回node就好。

function reConstructBinaryTree(pre, vin){
    var fi = 0;
    if(pre.length == 0){
      return;
    }else{
      for(var i=0;i<vin.length;i++){
        if(pre[0] === vin[i]) {fi=i;break;}
      }
      var lv = vin.slice(0,fi);
      var rv = vin.slice(fi+1, vin.length);
      var lp = pre.slice(1, 1+lv.length);
      var rp = pre.slice(1+lv.length, pre.length);
      var node = {
        val:pre[0],
        left:reConstructBinaryTree(lp, lv),
        right:reConstructBinaryTree(rp, rv)
      };
      console.log(node);
      return node;
    }
}

对比见高下(T_T)

function TreeNode(x) {    
  this.val = x;    
  this.left = null;    
  this.right = null;
} */
function reConstructBinaryTree(pre, vin){
   if (!pre || pre.length === 0) {       
    return;    
  }    
  var treeNode = {
    val: pre[0]    
  }    
  for(var i = 0; i < pre.length; i++) {        
    if (vin[i] === pre[0]) {            
      treeNode.left = reConstructBinaryTree(pre.slice(1, i+1), vin.slice(0, i));            
      treeNode.right = reConstructBinaryTree(pre.slice(i+1),vin.slice(i+1));        
    }   
   }    
  return treeNode;    
  console.log(treeNode)
}
module.exports = {    reConstructBinaryTree : reConstructBinaryTree};

https://www.nowcoder.com/profile/977454/codeBookDetail?submissionId=8750693