/**
* 前序遍历和中序遍历的结果还原一棵二叉树，很经典的问题
*/
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 }
}
}
