题目来源：力扣（LeetCode）

题目

根据一棵树的前序遍历与中序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如，给出

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

  1.         3
  2.    / \
  3.   9  20
  4.     /  \
  5.    15   7

思路分析

在讲解具体的思路之前，我们先来了解一下什么是前序遍历，什么是中序遍历。

前序遍历的顺序为：

  1. 先遍历根节点；
  2. 然后递归地遍历左子树
  3. 最后递归地遍历右子树

中续遍历的顺序为：

  1. 先递归的遍历左子树；
  2. 然后遍历根节点；
  3. 最后递归地遍历右子树；

在 递归 地遍历某个子树的过程中，我们也是将这棵子树看成是一棵全新的树，按照 前序遍历 或 中序遍历 的顺序进行遍历。

对于任意一棵树而言，前序遍历的形式总是：

[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]

即根节点总是前序遍历中的第一个节点，因此在 preorder = [3,9,20,15,7] 中，3 就是整棵树的根节点。

而中序遍历的形式总是：

[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]

即根节点是中序遍历中的第二个节点，那么在 inorder = [9,3,15,20,7] 中，3 就是整棵树的根节点。

只要我们在中序遍历中定位到根节点，那么我们就可以分别知道左子树和右子树中的节点数目。

只要我们在中序遍历中定位到根节点，那么我们就可以分别知道左子树和右子树中的节点数目。由于同一颗子树的前序遍历和中序遍历的长度显然是相同的，因此我们就可以对应到前序遍历的结果中，对上述形式中的所有左右括号进行定位。

这样以来，我们就知道了左子树的前序遍历和中序遍历结果，以及右子树的前序遍历和中序遍历结果，我们就可以递归地对构造出左子树和右子树，再将这两颗子树接到根节点的左右位置。

详细步骤：

  1. 根据前序遍历的特性可知，前序遍历数组的第一个元素，就是整棵树的根节点，我们获取到了根节点的值；
  2. 同样根据中序遍历的特性可知，中序遍历数组的第二个元素，就是整棵树的根节点，我们找到根节点在数组中的位置 mid，就可以分隔左右子树了，其中左子树：isStart ~ mid - 1，右子树：mid + 1 ~ inorder.length - 1；
  3. 我们将中序遍历数组的元素及其位置存储在哈希表中，以帮助我们快速地定位根节点。对于哈希映射中的每个键值对，健表示一个元素 (节点的值)，值表示其在中序遍历数组中的位置；
  4. 在中序遍历数组中，我们定位到了根节点的位置，然后根据根节点的位置来获取左子树的节点个数 leftNum，从而通过 leftNum 来获取在前序遍历数组中左子树和右子树的分割点；那么在前序遍历中，左子树为：pstart + 1 ~ pstart + leftNum ，右子树：pstart + leftNum + 1 ~ preorder.length - 1
  5. 然后，我们递归地构造出左子树和右子树，再将这两棵子树接到根节点的左右位置。
  1. const buildTree = function(preorder, inorder) {
  3.   // 将中序遍历数组的元素及其位置存储在哈希表中，以帮助我们快速地定位根节点
  4.     const map = new Map();
  5.   for (let i = 0; i< inorder.length; i++) {
  6.       map.set(inorder[i], i);
  7.   }
  9.   /**
  10.    * @param {number} pStart  左子树或右子树的在前序遍历数组中开始位置
  11.    * @param {number} pEnd    左子树或右子树的在前序遍历数组中结束位置
  12.    * @param {number} iStart  左子树或右子树的在中序遍历数组中开始位置
  13.    * @param {number} iEnd    左子树或右子树的在中序遍历数组中结束位置
  14.    * @return {TreeNode}
  15.    */
  16.   const helper = (pStart, pEnd, iStart, iEnd) => {
  17.     // 当索引值 pStart 大于 pEnd 的时候，证明我们的前序遍历数组已经使用完毕
  18.       if (pStart > pEnd) return null;
  19.     // 从前序遍历数组中获取根节点的值
  20.     let rootVal = preorder[pStart];
  21.     // 构造一个根节点
  22.     let root = new TreeNode(rootVal);
  23.     // 获取根节点在中序遍历数组中的索引位置，来分隔左右子树
  24.     let mid = map.get(rootVal);
  25.     // 计算左子树的节点个数，用来在前序遍历数组中确定左子树结束的位置
  26.     let leftNum = mid - iStart;
  27.     // 递归地构建左子树
  28.     root.left = helper(pStart + 1, pStart + leftNum, iStart, mid - 1);
  29.     // 递归的构建右子树
  30.     root.right = helper(pStart + leftNum + 1, pEnd, mid + 1, iEnd);
  31.     return root;
  32.   }
  34.   return helper(0, preorder.length -1, 0, inorder.length - 1);
  35. }