[JS]前序遍历和中序遍历的结果还原一棵二叉树，很经典的问题

/**
 * 前序遍历和中序遍历的结果还原一棵二叉树，很经典的问题
 */
function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}

/**
 * 根据前序和中序的结果还原二叉树
 * @param {*} pre 前序遍历的序列
 * @param {*} vin 中序遍历的序列
 */
function buildTree(pre, vin){
    // console.log('=======start=========')
    if(pre.length == 0 || vin.length == 0){
        return null
    }
    // 1)根据前序遍历的第一个节点就是原二叉树的根节点，求得根节点是 1
    var index = vin.indexOf(pre[0]); //获取根结点索引
   
    // 2)根据中序遍历，根节点左边就是左子树的节点，求得左树的范围 [4,7,2]
    var leftTree = vin.slice(0, index); //左树的范围
    
    var rightTree = vin.slice(index+1); //右树的范围
    

    //新建二叉树
    var node = new TreeNode(vin[index]) //根节点以及后续迭代的各节点
    node.left = buildTree(pre.slice(1, index+1), leftTree)
    node.right = buildTree(pre.slice(index+1), rightTree);
  
    return node;
}


//测试用例
// buildTree([1,2,4,7,3,5,6,8],[4,7,2,1,5,3,8,6])
console.log('最终还原的二叉树为：',buildTree([1,2,4,7,3,5,6,8],[4,7,2,1,5,3,8,6]))

最终还原的二叉树为： TreeNode {
val: 1,
right: TreeNode {
val: 3,
right: TreeNode { val: 6, right: null, left: [TreeNode] },
left: TreeNode { val: 5, right: null, left: null }
},
left: TreeNode {
val: 2,
right: null,
left: TreeNode { val: 4, right: [TreeNode], left: null }
}
}