重建二叉树

需求

根据前序遍历和中序遍历来构建一颗二叉树

前序遍历:根左右 1,2,4,7,3,5,6,8

中序遍历:左根右 4,7,2,1,5,3,8,6

思路

找到根节点

找到根节点的下标序号

从根节点区分开左子树和右子树

递归构建左右子树

当左右子树为空时，退出

代码

let arr1 = [1,2,4,7,3,5,6,8]  //前序遍历
let arr2 = [4,7,2,1,5,3,8,6]  //中序遍历
function TreeNode(val){
    this.val = val;
    this.left = null;
    this.right = null;
}
function buildTree(arr1,arr2){
    let rootval = arr1[0];  //根节点的值
    if(rootval){
        let root = new TreeNode(rootval); //根节点
        let index = arr2.indexOf(rootval);
        let left_inorder = arr2.slice(0,index);  //中序遍历左子树
        let right_inorder = arr2.slice(index+1);  //中序遍历右子树
        let left_preorder = arr1.slice(1,index+1); //先序遍历左子树
        let right_preorder = arr1.slice(index+1);  //先序遍历右子树
        root.left = buildTree(left_preorder,left_inorder);
        root.right = buildTree(right_preorder,right_inorder);
        return root;
    }
    return null; //退出递归，子树为空
}