题解 | 重建二叉树

前序遍历判断根节点，中序遍历判断左右

[1,2,4,7,3,5,6,8],[4,7,2,1,5,3,8,6]

根节点为 1, 中序遍历判断位置，对数组进行左右切分 [4,7,2][5,3,8,6],前序遍历同样切分 [2,4,7] [3,5,6,8]

1、左子树：[2,4,7] [4,7,2]

前序遍历第一个2 就为 root 的左节点，然后已 2 再为根节点重复上述操作：

中序遍历切分：[4,7] [] 前端遍历切分：[4,7][] ,重复执行....

2、右子树：[3,5,6,8] [5,3,8,6]同样直接上述操作：

前序遍历第一个 3 就为 root 的右节点 , 重复执行....

/*
 * function TreeNode(x) {
 *   this.val = x;
 *   this.left = null;
 *   this.right = null;
 * }
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param preOrder int整型一维数组
 * @param vinOrder int整型一维数组
 * @return TreeNode类
 */
function reConstructBinaryTree(preOrder, vinOrder) {
    console.log("-----");
    console.log(preOrder, vinOrder);
    if (!preOrder.length || !vinOrder.length) return null;
    // write code here
    const root = new TreeNode(preOrder[0]);
    const midIndex = vinOrder.indexOf(preOrder[0]);
    root.left = reConstructBinaryTree(
        preOrder.slice(1, midIndex + 1),
        vinOrder.slice(0, midIndex)
    );
    root.right = reConstructBinaryTree(
        preOrder.slice(midIndex + 1),
        vinOrder.slice(midIndex + 1)
    );
    return root;
}
module.exports = {
    reConstructBinaryTree: reConstructBinaryTree,
};