image.png

image.png

一、破题思路

前序遍历：根→左→右
中序遍历：左→根→右
1、前序序列[1,2,4,7,3,5,6,8]，根节点为1
2、中序序列[4,7,2,1,5,3,8,6]，找到根节点1，根节点左侧为左子树，根节点右侧为右子树
3、将左子树和右子树分别看成1棵树，递归1，2两步
4、递归调用的终止条件，左子树或者右子树为空（长度为0）

二、js代码实现

function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
}
function reConstructBinaryTree(pre, vin)
{
    if(pre.length == 0 || vin.length == 0){return null}
    //从前序遍历中拿到根节点
    let root = new TreeNode(pre[0]);
    //根节点在中序遍历数组中的下标
    let i = vin.indexOf(root.val)
    //中序遍历拿到左子树和右子树
    root.left = reConstructBinaryTree(pre.slice(1,i+1),vin.slice(0,i))
    root.right = reConstructBinaryTree(pre.slice(i+1,pre.length),vin.slice(i+1,vin.length))
       
    return root
    
}
module.exports = { 
    reConstructBinaryTree : reConstructBinaryTree
};

三、运行结果

image.png