根据前序和中序遍历构造二叉树，为什么天然是分治？

简化版

前序遍历的第一个元素是根节点，中序遍历中根节点左边是左子树，右边是右子树。

因此可以用根节点把问题切成左右两棵子树，递归构造。

为了快速在中序数组中找到根节点位置，通常用哈希表保存值到下标的映射。

详细版

前序遍历顺序是：根、左、右。中序遍历顺序是：左、根、右。

递归时先从前序数组拿当前根值，再去中序数组中找到根的位置。中序左侧元素数量就是左子树大小，右侧元素数量就是右子树大小。

有了左子树大小，就能在前序数组中切分出左子树和右子树对应区间。

递归函数可以接收前序区间和中序区间，返回构造好的根节点。

时间复杂度 O(n)，空间复杂度 O(n)。

完整版教学

一、两种遍历各提供什么信息

前序遍历最有价值的信息是根节点，因为它第一个访问根。中序遍历最有价值的信息是左右子树边界，因为根节点左边全属于左子树，右边全属于右子树。单独看一个遍历通常不够，二者结合才能递归切分树。

记忆钩子：前序负责找根，中序负责切左右。

二、为什么这是分治

构造整棵树，可以拆成构造左子树和右子树。找到根以后，中序数组自然分裂成两个互不重叠的区间；前序数组也能根据左子树大小切成对应区间。左右子树结构与原问题相同，所以递归成立。

信息	作用	分治意义
前序首元素	当前根	确定中心
中序根下标	左右边界	拆成子问题
左子树大小	切前序区间	保持两种遍历同步

切分正确，整棵树就能还原。

三、区间怎么计算

假设前序区间是 [preL, preR]，中序区间是 [inL, inR]。根值是 preorder[preL]，它在中序中的位置是 idx。左子树大小：

leftSize = idx - inL

于是左子树前序区间是 [preL+1, preL+leftSize]，右子树前序区间是 [preL+leftSize+1, preR]。

四、代码模板

实现如下：

function buildTree(preorder, inorder) {
  const pos = new Map()
  for (let i = 0; i < inorder.length; i++) pos.set(inorder[i], i)

  function build(preL, preR, inL, inR) {
    if (preL > preR) return null
    const rootVal = preorder[preL]
    const idx = pos.get(rootVal)
    const leftSize = idx - inL
    const root = new TreeNode(rootVal)
    root.left = build(preL + 1, preL + leftSize, inL, idx - 1)
    root.right = build(preL + leftSize + 1, preR, idx + 1, inR)
    return root
  }

  return build(0, preorder.length - 1, 0, inorder.length - 1)
}

哈希表让查根位置从 O(n) 降到 O(1)。

五、带数字例子

前序 [3,9,20,15,7]，中序 [9,3,15,20,7]。前序首元素 3 是根，在中序下标 1，左边 [9] 是左子树，右边 [15,20,7] 是右子树。右子树前序对应 [20,15,7]，继续递归，20 成为右子树根。

这个过程每一层都在找根和切区间。

六、常见误区与追问

误区：只用前序就想唯一构造树。 没有中序边界，左右子树划分不唯一。
误区：每次在线性扫描中序。 会让总复杂度退化到 O(n^2)。
误区：左右子树前序区间切错。 必须用左子树大小同步两个遍历数组。
追问：如果节点值重复怎么办？ 标准题通常保证值唯一；有重复值时映射不唯一，需要额外信息。
追问：前序+后序能唯一构造吗？ 普通二叉树通常不能，满二叉树等附加条件下才可能。

这些追问都围绕“遍历信息是否足够唯一”。

七、加强记忆

构造树记成“前序拿根，中序切半，左大小切前序”。根把问题分成左右子树，左右再递归构造。哈希表缓存中序位置，避免每层扫描。只要区间边界算准，这题就是非常标准的二叉树分治。

简化版

详细版