重建二叉树（JS实现）
题目
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
/* function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
} */
function reConstructBinaryTree(pre, vin)
{
//在此作答
}
思路
二叉树的前序遍历第一个节点，即为根节点。找到中序遍历中根节点的位置，其左边的序列即为其左子树，右边的序列即为右子树，这样就把原序列划分为两个子序列，分别对两个子序列进行递归操作，就成功地构造了二叉树
代码
function reConstructBinaryTree(pre, vin)
{
if (pre.length === 0) return; //如果前序遍历为空，说明已经没有节点了
var root = new TreeNode(pre[0]); //生成根节点
var root_index = vin.indexOf(root.val); //找到根节点在中序遍历中的位置
root.left = reConstructBinaryTree(pre.slice(1,root_index+1), vin.slice(0,root_index)); //递归生成左子树
root.right = reConstructBinaryTree(pre.slice(root_index+1), vin.slice(root_index+1)); //递归生成右子树
return root;
}
