描述

给定节点数为 n 的二叉树的前序遍历和中序遍历结果，请重建出该二叉树并返回它的头结点。

例如输入前序遍历序列{1, 2, 4, 7, 3, 5, 6, 8}和中序遍历序列{4, 7, 2, 1, 5, 3, 8, 6}，则重建出如下图所示。

     1
    / \
   2   3
  /   / \
 4   5   6
  \     /
   7   8

链接

BM40 重建二叉树 Nowcoder

示例

输入：[1,2,4,7,3,5,6,8],[4,7,2,1,5,3,8,6]
返回值：{1,2,3,4,#,5,6,#,7,#,#,8}
说明：返回根节点，系统会输出整颗二叉树对比结果，重建结果如题面图示    

输入：[1],[1]
返回值：{1}

输入：[1,2,3,4,5,6,7],[3,2,4,1,6,5,7]
返回值：{1,2,5,3,4,6,7}

题解

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

[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) {
    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,
};