[数据结构与算法][JavaScript]重建二叉树

描述

给定节点数为 n 二叉树的前序遍历和中序遍历结果，请重建出该二叉树并返回它的头结点。
例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出如下图所示。

提示:

• 1.vin.length == pre.length
• 2.pre 和 vin 均无重复元素
• 3.vin出现的元素均出现在 pre里
• 4.只需要返回根结点，系统会自动输出整颗树做答案对比

代码

• 1.先找中序中的结点
• 2.找到后就可以找左右结点了
• 3.递归就可以得到二叉树了

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function reBuild(pre,vin,p_left,p_right,v_left,v_right){
    if(p_left>p_right) return null
    let index=0
    for(let i=v_left;i<=v_right;i++){
        if(vin[i]==pre[p_left]){
            index=i
            break
        }
    }
    let node=new TreeNode(vin[index])
    node.left=reBuild(pre,vin,p_left+1,p_left+index-v_left,v_left,index-1)
    node.right=reBuild(pre,vin,p_left+index-v_left+1,p_right,index+1,v_right)
    return node
}
function reConstructBinaryTree(pre, vin)
{
    // write code here
    return reBuild(pre,vin,0,pre.length-1,0,vin.length-1)
}
module.exports = {
    reConstructBinaryTree : reConstructBinaryTree
};