使用 JavaScript 解答 LeetCode 第 105 题，从前序与中序遍历序列构造二叉树，中等难度。

原题

原题链接

本题是 LeetCode 题库第 105 题，由此访问。

题目描述

根据一棵树的前序遍历与中序遍历构造二叉树。你可以假设树中没有重复的元素。

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7

解题

AC 样例

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function(preorder, inorder) {
    if(!preorder || inorder.length < 1) return null;
    const index = preorder.shift();
    const node = new TreeNode(index);

    const n = inorder.indexOf(index);
    const leftTree = inorder.slice(0, n);
    const rightTree = inorder.slice(n+1);

    node.left = buildTree(preorder, leftTree);
    node.right = buildTree(preorder, rightTree);
    return node;
};

解题思路

这个题目考察的内容非常基础，主要是二叉树的概念，树的遍历次序和规律。

根据前序遍历的规则，根节点位于遍历序列第一位，其后分别是左右子树。对应到中序遍历序列中，位于根节点左侧的数据即为具体的左子树节点，其右侧为具体的右子树节点。若子树节点有多个，则返回前序遍历序列中查找该子树的根节点，进一步缩小数据规模。

每一个子树均按照相同的规则构建，自上而下的构建完成后便得到符合要求的二叉树。