剑指offer之重建二叉树（JS实现）
最近在补强算法，把自己遇到困难的解决过程通过笔记的方式记录下来，希望能让自己有小小的提高同时也希望可以帮助到有需要的人~
题目描述
重建二叉树 (难度:中等 标签：树、递归）
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
思路：解决树的题，先想到递归的思想。
例如：
先根序遍历: GDAFEMHZ
中序遍历: ADEFGHMZ
- 第一步，根据先根序序遍历的特点，我们知道根结点为G
- 第二步，观察中序遍历ADEFGHMZ。其中root节点G左侧的ADEF必然是root的左子树，G右侧的HMZ必然是root的右子树。
- 第三步，观察左子树为ADEF，长度为4，则先根序遍历中的DAFE（长度为4）为左子树，D排在最前则为左子树的根节点
- 第四步，同样的道理，root的右子树节点HMZ中的根节点也可以通过前序遍历求得。在先根序序遍历中，一定是先把root和root的所有左子树节点遍历完之后才会遍历右子树，并且遍历的左子树的第一个节点就是左子树的根节点。同理，遍历的右子树的第一个节点就是右子树的根节点。
- 第五步，观察发现，上面的过程是递归的。先找到当前树的根节点，然后划分为左子树，右子树，然后进入左子树重复上面的过程，然后进入右子树重复上面的过程。最后就可以还原一棵树了。该步递归的过程可以简洁表达如下：
- 确定根,确定左子树，确定右子树。
- 在左子树中递归。
- 在右子树中递归。
- 打印当前根。
代码:
function reConstructBinaryTree(pre, vin) {
// write code here
if( pre.length === 0 || vin.length === 0){ //递归终止条件判断
return null
}
const index=vin.indexOf(pre[0]), //判断根节点在中序遍历的位置
left=vin.slice(0,index), //左子树
right=vin.slice(index+1); //右子树
return {
val : pre[0], //当前节点的值
left : reConstructBinaryTree(pre.slice(1,index+1),left), //左子树
right : reConstructBinaryTree(pre.slice(index+1),right) //右子树
}
}
复制代码若有不正确的地方，欢迎留言交流指正
