105.Construct Binary Tree from Preorder and Inorder Traversal

/**
 * 根据前序遍历和中序遍历的结果构建二叉树
 * @param {number[]} preorder - 二叉树的前序遍历数组（根 -> 左 -> 右）
 * @param {number[]} inorder - 二叉树的中序遍历数组（左 -> 根 -> 右）
 * @returns {TreeNode} - 构建完成的二叉树根节点
 */
var buildTree = function (preorder, inorder) {
  // 获取当前子树的节点总数
  const n = preorder.length

  // 递归终止条件：如果节点数为0，说明当前子树为空，返回null
  if (n === 0) {
    return null
  }

  // 前序遍历的第一个元素就是当前子树的根节点值
  const rootVal = preorder[0]
  // 在中序遍历数组中找到根节点的索引，该索引左侧是左子树的所有节点，右侧是右子树的所有节点
  const rootIndexInInorder = inorder.indexOf(rootVal)
  // 左子树的节点数量 = 根节点在中序数组中的索引值
  const leftSubtreeSize = rootIndexInInorder

  // 分割前序数组：前序数组中，根节点之后的leftSubtreeSize个元素是左子树的前序遍历结果
  const leftPreorder = preorder.slice(1, 1 + leftSubtreeSize)
  // 分割前序数组：剩余的元素是右子树的前序遍历结果
  const rightPreorder = preorder.slice(1 + leftSubtreeSize)

  // 分割中序数组：根节点左侧的所有元素是左子树的中序遍历结果
  const leftInorder = inorder.slice(0, rootIndexInInorder)
  // 分割中序数组：根节点右侧的所有元素是右子树的中序遍历结果
  const rightInorder = inorder.slice(rootIndexInInorder + 1, n)

  // 递归构建左子树
  const leftSubtree = buildTree(leftPreorder, leftInorder)
  // 递归构建右子树
  const rightSubtree = buildTree(rightPreorder, rightInorder)

  // 创建当前层的根节点，关联其左、右子树，并返回该节点
  return new TreeNode(rootVal, leftSubtree, rightSubtree)
}

/**
 * 优化版：根据前序遍历和中序遍历结果构建二叉树
 * 核心优化点：
 * 1. 用Map缓存中序遍历值与索引的映射，避免每次递归调用indexOf（时间复杂度从O(n²)降为O(n)）
 * 2. 用下标区间代替数组切片，减少内存拷贝（空间复杂度优化）
 * @param {number[]} preorder - 二叉树的前序遍历数组（根 -> 左 -> 右）
 * @param {number[]} inorder - 二叉树的中序遍历数组（左 -> 根 -> 右）
 * @returns {TreeNode} - 构建完成的二叉树根节点
 */
var buildTree = function (preorder, inorder) {
  // 获取节点总数（前序/中序数组长度一致）
  const n = preorder.length

  // 创建Map字典，缓存中序遍历数组中「值 -> 索引」的映射
  // 目的：O(1)时间查找根节点在中序数组中的位置，替代频繁的indexOf调用
  const valueToInorderIndex = new Map()
  for (let i = 0; i < n; i++) {
    valueToInorderIndex.set(inorder[i], i)
  }

  /**
   * 深度优先递归构建子树（核心递归函数）
   * 采用「左闭右开」区间规则：[preL, preR) 表示前序数组的有效范围，[inL, inR) 表示中序数组的有效范围
   * @param {number} preL - 前序数组当前子树的左边界（包含）
   * @param {number} preR - 前序数组当前子树的右边界（不包含）
   * @param {number} inL - 中序数组当前子树的左边界（包含）
   * @returns {TreeNode} 当前子树的根节点
   */
  function dfs(preL, preR, inL) {
    // 递归终止条件：前序区间左边界等于右边界，说明当前子树无节点，返回null
    // （左闭右开区间 [preL, preR) 为空的条件）
    if (preL === preR) {
      return null
    }

    // 1. 确定当前子树的根节点值：前序区间的第一个元素（preL位置）
    const rootVal = preorder[preL]
    // 2. 从Map中快速获取根节点在中序数组中的索引（O(1)时间）
    const rootInorderIndex = valueToInorderIndex.get(rootVal)
    // 3. 计算左子树的节点数量：根节点在中序数组中的索引 - 中序区间左边界
    const leftSubtreeSize = rootInorderIndex - inL

    // 4. 递归构建左子树
    // 前序区间：[preL+1, preL+1+leftSubtreeSize) （根节点后紧跟左子树）
    // 中序区间：[inL, rootInorderIndex) （中序数组中根节点左侧为左子树）
    const leftSubtree = dfs(preL + 1, preL + 1 + leftSubtreeSize, inL)

    // 5. 递归构建右子树
    // 前序区间：[preL+1+leftSubtreeSize, preR) （左子树之后为右子树）
    // 中序区间：[rootInorderIndex+1, inL + (preR - preL)) （简化为 inL + 1 + leftSubtreeSize）
    const rightSubtree = dfs(preL + 1 + leftSubtreeSize, preR, inL + 1 + leftSubtreeSize)

    // 6. 创建当前根节点，关联左右子树并返回
    return new TreeNode(rootVal, leftSubtree, rightSubtree)
  }

  // 初始调用递归函数：
  // 前序区间 [0, n) 表示整个前序数组，中序左边界 inL=0 表示从中序数组起始位置开始
  return dfs(0, n, 0)
}