LeetCode题解：105. 从前序与中序遍历序列构造二叉树，递归+哈希表，JavaScript，详细注释

[chencl1986]

原题链接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

解题思路：

1. 参考了多种解法，逐渐优化（补充国外大佬解法）和动画演示 105. 从前序与中序遍历序列构造二叉树。
2. 假设有一个二叉树如下：

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

前序遍历的结果是: [1,2,4,5,3,6,7]
中序遍历的结果是: [4,2,5,1,6,3,7]

3. 可以将其从根节点1，拆分成两个子树，如下：

左子树：

	   2
	  / \
	 4   5

前序遍历的结果是: [2,4,5]
中序遍历的结果是: [4,2,5]

右子树：

	   3
	  / \ 
	 6   7

前序遍历的结果是: [3,6,7]
中序遍历的结果是: [6,3,7]

4. 我们可以按照步骤3的规律，计算出左右子树的前中序遍历对应在原数组中的索引，即可知道它们对应的值：

   • 左子树的前序遍历索引：

   preLeft = preLeft + 1, // 左子树的前序遍历左边界
   preRight = preLeft + nodeCount, // 当前左边界加上子树节点数量，即为左子树的前序遍历右边界
   

   • 左子树的中序遍历索引：

   inLeft = inLeft, // 左子树的中序遍历左边界
   inRight = rootIndex - 1, // 左子树的中序遍历右边界
   

   • 右子树的前序遍历索引：

   preLeft = preLeft + nodeCount + 1, // 当前左边界加上子树节点数量再加1，即为右子树的前序遍历左边界
   preRight = preRight, // 右子树的前序遍历右边界
   

   • 右子树的中序遍历索引：

   inLeft = rootIndex + 1, // 右子树的中序遍历左边界
   inRight = inRight, // 右子树的中序遍历右边界
   

5. 经过步骤4的分析，我们可以按照以下逻辑进行递归：

   • 每次递归用preorder[preLeft]的值生成一个根节点。
   • 在通过preorder[preLeft]找到其在inorder中的位置rootIndex，计算出子树的前中序遍历在原数组中的索引，分别进行下一层的递归。
   • 每次递归时，inorder中每个值的位置都是固定的，因此只需要在递归之前用Map缓存所有值与索引的关系，之后用O(1)的时间复杂度即可完成查询。
   • 将下层递归生成的左右子树，连接到当前根节点上。
   • 递归完成时将当前根节点返回，供上一层递归连接。
   • preorder和inorder中的所有值都生成过节点之后，也就完成了整个二叉树的生成。

/**
 * 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) {
  /**
   * @description 使用前中序遍历结果的片段，递归生成二叉树
   * @param {number} preLeft // 每个子树在前序遍历中的左边界
   * @param {number} preRight // 每个子树在前序遍历中的右边界
   * @param {number} inLeft // 每个子树在中序遍历中的左边界
   * @param {number} inRight // 每个子树在中序遍历中的右边界
   * @return {TreeNode}
   */
  function buildBinaryTree(preLeft, preRight, inLeft, inRight) {
    // 当截取数组片段的左边界大于右边界时，表示当前用于构造子树的数组为空，退出循环
    if (preLeft > preRight) {
      // 数组为空时，表示当前已经无节点需要生成，返回null
      // 让上一层节点的left和right指针指向null
      return null;
    }

    // 缓存根节点的值
    const rootVal = preorder[preLeft];
    // 使用当前值创建一个节点，即为一个树的根节点
    const root = new TreeNode(rootVal);
    // 查找到当前根节点在数组中的位置
    const rootIndex = inorder.indexOf(rootVal);
    // 中序遍历的左边界到根节点之差是子树的节点数量
    // 由于左边界始终会存在，因此向左统计总是可以得到子树的节点数量
    const nodeCount = rootIndex - inLeft;

    // 计算数组对应左子树的索引，向下递归
    // 将当前根节点与已生成好的左子树连接
    root.left = buildBinaryTree(
      preLeft + 1, // 左子树的前序遍历左边界
      preLeft + nodeCount, // 当前左边界加上子树节点数量，即为左子树的前序遍历右边界
      inLeft, // 左子树的中序遍历左边界
      rootIndex - 1, // 左子树的中序遍历右边界
    );
    // 计算数组对应右子树的索引，向下递归
    // 将当前根节点与已生成好的右子树连接
    root.right = buildBinaryTree(
      preLeft + nodeCount + 1, // 当前左边界加上子树节点数量再加1，即为右子树的前序遍历左边界
      preRight, // 右子树的前序遍历右边界
      rootIndex + 1, // 右子树的中序遍历左边界
      inRight, // 右子树的中序遍历右边界
    );

    // 将根节点返回供上层节点连接
    return root;
  }

  // 生成二叉树并返回
  return buildBinaryTree(0, preorder.length - 1, 0, preorder.length - 1);
};