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
