题目描述

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：

  1. 3<br />   / \<br />  9  20<br />    /  \<br />   15   7<br />

限制：

0 <= 节点个数 <= 5000

注意：本题与主站 105 题重复：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

let inHash = {};
let po = null;

/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function(preorder, inorder) {
    // 前序保存到全局中
    po = preorder;
    // 把中序写到hash中，值 => 位置
    for (let i = 0; i < inorder.length; i++) {
        inHash[inorder[i]] = i;
    }
    return rebuild(0, 0, inorder.length - 1);
};

/**
 * preOrderIdx - 前序遍历中根节点位置
 * inOrderLeft - 中序遍历中左边界位置
 * inOrderRight - 中序遍历中右边界位置
 */
function rebuild(preOrderIdx, inOrderLeft, inOrderRight) {
    // 防止越界，越界时代表已经无节点
    if (inOrderLeft > inOrderRight) return null;

    // 取出根节点在前序中的值
    let val = po[preOrderIdx];
    let node = new TreeNode(val);

    // 两个相等代表叶子结点了，直接返回node即可
    if (inOrderLeft < inOrderRight) {
        // 取出当前根节点在中序中的位置
        let inPreIdx = inHash[val];
        /* 
         * 前序中，左子树节点为前序位置中根节点的右边第一个 [3(根节点),9(左子树节点),20,15,7]
         * 中序中，左子树左边界为原左边界。
         * 中序中，左子树右边界为根节点左边第一个 [(左子树左边界)9(左子树右边界),3(根节点),15,20,7]
         */
        node.left = rebuild(preOrderIdx + 1, inOrderLeft, inPreIdx - 1);
        /** 
         * 前序中，右子树节点为左子树长度 + 根节点位置 + 1
         *        其中，左子树长度 = 左子树右边界 - 左子树左边界 + 1
         *        右子树节点 = (左子树右边界 - 左子树左边界 + 1) + 根节点位置 + 1
         *                  = (inPreIdx - 1 - inOrderLeft + 1) + preOrderIdx + 1
         * 中序中，右子树左边界为根节点右边第一个 [9,3(根节点),15(右子树节点),20,7]
         * 中序中，右子树右边界为原右边界。
         */
        node.right = rebuild(
            preOrderIdx + (inPreIdx - 1 - inOrderLeft + 1) + 1, 
            inPreIdx + 1, 
            inOrderRight
        );
    }

    return node;
}