题解 | #重建二叉树#

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function reConstructBinaryTree(pre, vin)
{
    // write code here
    if(pre.length === 0) return;

    const root = new TreeNode(pre[0]);
    const rInVinIndex = vin.findIndex(v => v === root.val);

    const lVin = vin.slice(0, rInVinIndex);
    const lPre = pre.slice(1, lVin.length + 1); 
    root.left = reConstructBinaryTree(lPre, lVin);

    const rPre = pre.slice(lPre.length + 1);
    const rVin = vin.slice(rInVinIndex + 1)；
    root.right = reConstructBinaryTree(rPre, rVin);

    return root;
}
module.exports = {
    reConstructBinaryTree
};

这道题在做的时候，有一个坑点：就是拿到的pre[0] 需要先转换成node，new TreeNode(pre[0])，趟过这个坑点，后续的代码就简单了。

我前面做过一个类似的题，打印右视图的那道题，那里我重构二叉树的时候，传入的是root，就传参已经是node了，就不需要上面的转换了。做这道题的时候以为是一样的，谁知道不一样，还是要仔细看传参！！！

重构二叉树的原理就简单了，就是现在一个先序中找到根，然后在两个数组中 确定左子树、右子树 就可以了。