/**
 * 前序遍歷和中序遍歷的結(jié)果還原一棵二叉樹，很經(jīng)典的問題
 */
function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}

/**
 * 根據(jù)前序和中序的結(jié)果還原二叉樹
 * @param {*} pre 前序遍歷的序列
 * @param {*} vin 中序遍歷的序列
 */
function buildTree(pre, vin){
    // console.log('=======start=========')
    if(pre.length == 0 || vin.length == 0){
        return null
    }
    // 1)根據(jù)前序遍歷的第一個(gè)節(jié)點(diǎn)就是原二叉樹的根節(jié)點(diǎn)，求得根節(jié)點(diǎn)是 1
    var index = vin.indexOf(pre[0]); //獲取根結(jié)點(diǎn)索引
   
    // 2)根據(jù)中序遍歷，根節(jié)點(diǎn)左邊就是左子樹的節(jié)點(diǎn)，求得左樹的范圍 [4,7,2]
    var leftTree = vin.slice(0, index); //左樹的范圍
    
    var rightTree = vin.slice(index+1); //右樹的范圍
    

    //新建二叉樹
    var node = new TreeNode(vin[index]) //根節(jié)點(diǎn)以及后續(xù)迭代的各節(jié)點(diǎn)
    node.left = buildTree(pre.slice(1, index+1), leftTree)
    node.right = buildTree(pre.slice(index+1), rightTree);
  
    return node;
}


//測(cè)試用例
// 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 }
}
}