0105. Construct Binary Tree from Preorder and Inorder Traversal
===============================================================
题目信息
--------
:题号: 0105. 从前序与中序遍历序列构造二叉树
:难度: Medium
:主题: 二叉树、分治、遍历序列、哈希索引
:原题: `LeetCode 0105 `_
:重点: 前序确定子树根,中序确定左右规模,再用区间和前序游标删除重复扫描与切片
题目重述
--------
给定两个长度相同的整数数组 ``preorder`` 和 ``inorder``,它们分别是一棵二叉树的前序遍历与中序遍历结果,
需要重建并返回这棵树。
前序遍历顺序是“根、左子树、右子树”,中序遍历顺序是“左子树、根、右子树”。两个数组包含完全相同的节点
值,所有值互不相同,且输入保证来自同一棵有效二叉树,因此重建结果唯一。数组长度在 ``1..3000`` 范围内,
节点值在 ``-3000..3000`` 范围内。
自建示例
--------
* 左右子树都存在:``preorder = [8,4,2,6,12,10]``、``inorder = [2,4,6,8,10,12]``,返回树的
层序表示为 ``[8,4,12,2,6,10]``;
* 完全左斜:``preorder = [5,4,3]``、``inorder = [3,4,5]``,返回 ``[5,4,null,3]``。每个根都在
当前中序区间最右侧;
* 完全右斜:``preorder = [3,4,5]``、``inorder = [3,4,5]``,返回 ``[3,null,4,null,5]``;
* 单节点:``preorder = [7]``、``inorder = [7]``,返回只含根节点 ``7`` 的树。
C++ 实现
--------
.. code-block:: cpp
#include
#include
class Solution {
private:
TreeNode* buildWithSlices(const std::vector& preorder, const std::vector& inorder) {
if (preorder.empty()) {
return nullptr;
}
const int rootValue = preorder.front();
int split = 0;
while (inorder[split] != rootValue) {
++split;
}
const std::vector leftPreorder(preorder.begin() + 1, preorder.begin() + 1 + split);
const std::vector rightPreorder(preorder.begin() + 1 + split, preorder.end());
const std::vector leftInorder(inorder.begin(), inorder.begin() + split);
const std::vector rightInorder(inorder.begin() + split + 1, inorder.end());
TreeNode* root = new TreeNode(rootValue);
root->left = buildWithSlices(leftPreorder, leftInorder);
root->right = buildWithSlices(rightPreorder, rightInorder);
return root;
}
TreeNode* buildWithRanges(const std::vector& preorder, int preBegin, int preEnd, int inBegin,
int inEnd, const std::unordered_map& inorderIndex) {
if (preBegin == preEnd) {
return nullptr;
}
const int rootValue = preorder[preBegin];
const int split = inorderIndex.at(rootValue);
const int leftSize = split - inBegin;
TreeNode* root = new TreeNode(rootValue);
root->left = buildWithRanges(preorder, preBegin + 1, preBegin + 1 + leftSize, inBegin, split,
inorderIndex);
root->right = buildWithRanges(preorder, preBegin + 1 + leftSize, preEnd, split + 1, inEnd,
inorderIndex);
return root;
}
TreeNode* buildWithCursor(const std::vector& preorder, int& preorderCursor, int inBegin, int inEnd,
const std::unordered_map& inorderIndex) {
if (inBegin == inEnd) {
return nullptr;
}
const int rootValue = preorder[preorderCursor++];
const int split = inorderIndex.at(rootValue);
TreeNode* root = new TreeNode(rootValue);
root->left = buildWithCursor(preorder, preorderCursor, inBegin, split, inorderIndex);
root->right = buildWithCursor(preorder, preorderCursor, split + 1, inEnd, inorderIndex);
return root;
}
public:
TreeNode* buildTree(std::vector& preorder, std::vector& inorder) {
std::unordered_map inorderIndex;
inorderIndex.reserve(inorder.size());
for (int index = 0; index < static_cast(inorder.size()); ++index) {
inorderIndex[inorder[index]] = index;
}
int preorderCursor = 0;
return buildWithCursor(preorder, preorderCursor, 0, static_cast(inorder.size()), inorderIndex);
}
};
题解
----
两份序列的信息差
~~~~~~~~~~~~~~~~
只看前序序列时,当前第一个值一定是根,却不知道后面多少个值属于左子树;只看中序序列时,根一旦确定就能
划分左右子树,却不知道哪个值应当作为根。两份序列恰好补足彼此缺失的信息。
对任意非空子树,前序片段的首值 ``rootValue`` 是子树根。它在对应中序片段中的位置把片段唯一分成:
.. code-block:: text
inorder = [左子树节点 | rootValue | 右子树节点]
所有节点值互不相同,因此根在中序序列中只有一个位置,左右节点集合和规模随之确定。随后对两侧片段重复
同一过程,就能把原问题拆成两个更小、互不重叠的重建问题。
切片重建
~~~~~~~~
``buildWithSlices`` 是最接近定义的实现。取 ``preorder[0]`` 作为根,在线性扫描中序数组找到 ``split``;
中序左侧有 ``split`` 个值,所以前序中紧跟根的 ``split`` 个值必然属于左子树,余下值属于右子树。复制出
四个子数组后分别递归,空前序数组对应空子树。
这个方案正确的关键不是两个数组恰好切成相同下标,而是左子树节点数在两种遍历中相同。前序的左右边界由
中序左片段长度推导;若直接按中序的 ``split`` 当作所有递归层的前序绝对下标,子树起点变化后就会错位。
切片方案会重复两类工作:每个子问题都扫描中序片段寻找根,并复制新的前序、中序数组。完全斜树每次只缩短
一个元素,扫描量和复制量形成 ``n + (n - 1) + ... + 1``,最坏达到 ``O(n²)``。
区间替代切片
~~~~~~~~~~~~
数组内容不需要改变,递归只需知道当前片段边界。``buildWithRanges`` 使用半开区间
``[preBegin, preEnd)`` 与 ``[inBegin, inEnd)`` 表示同一子树,空区间由 ``preBegin == preEnd`` 判断。
再预先建立 ``节点值 -> 中序下标`` 的 ``inorderIndex``,根位置由重复线性扫描变为一次查询。设
``split`` 为根的中序下标,则 ``leftSize = split - inBegin``,四个孩子区间为:
.. code-block:: text
左子树 preorder:[preBegin + 1, preBegin + 1 + leftSize)
左子树 inorder :[inBegin, split)
右子树 preorder:[preBegin + 1 + leftSize, preEnd)
右子树 inorder :[split + 1, inEnd)
区间方案删除了所有子数组复制,哈希索引删除了重复找根;代价是每个状态同时维护四个边界,并在代码中计算
左子树规模以对齐两份序列。
前序游标压缩
~~~~~~~~~~~~
前序遍历本身已经规定了节点消费顺序:先根,再完整左子树,最后完整右子树。只要递归严格先构造左侧中序
区间、再构造右侧中序区间,一个全局 ``preorderCursor`` 就会自然依次指向每棵待建子树的根。
``buildWithCursor`` 因此只保留中序半开区间。进入非空区间时读取 ``preorder[preorderCursor]`` 并立即递增;
哈希索引给出左右中序边界,左递归会恰好消费左子树全部前序值,返回后游标自然停在右子树根。显式前序区间、
``leftSize`` 和右侧前序起点都从状态中消失。
左右递归顺序不能交换。读取根之后,游标指向的是前序中的左子树首值;若先传入右侧中序区间,这个左侧值会
被错误地用作右子树根。这里的调用顺序不是排版选择,而是维护“游标始终指向当前子树根”的不变量。
区间与游标走读
~~~~~~~~~~~~~~
对 ``preorder = [8,4,2,6,12,10]``、``inorder = [2,4,6,8,10,12]``:
.. list-table::
:header-rows: 1
* - 中序区间
- 游标读取
- 根位置
- 左区间
- 右区间
* - ``[0,6)``
- 8
- 3
- ``[0,3)``
- ``[4,6)``
* - ``[0,3)``
- 4
- 1
- ``[0,1)``
- ``[2,3)``
* - ``[0,1)``
- 2
- 0
- 空
- 空
* - ``[2,3)``
- 6
- 2
- 空
- 空
* - ``[4,6)``
- 12
- 5
- ``[4,5)``
- 空
* - ``[4,5)``
- 10
- 4
- 空
- 空
左子树返回时,游标已从 ``1`` 前进到 ``4``,正好指向值 ``12``,无需由根区间重新计算右子树前序起点。
单元素中序区间会创建叶节点,它的两个孩子调用都收到空区间并返回 ``nullptr``。
主解与复杂度
~~~~~~~~~~~~
公开入口采用前序游标方案,因为它保留“中序负责边界、前序负责根顺序”两个必要状态,删除了切片、前序边界
和子树规模换算。节点值唯一是哈希索引与唯一重建成立的前提;若存在重复值,单个值无法确定中序位置,当前
状态定义便不足以选择划分点。
切片方案最坏时间和额外复制量为 ``O(n²)``。两个区间方案都创建每个节点一次;在哈希表平均常数查询下,
期望时间为 ``O(n)``,索引工作空间为 ``O(n)``,递归栈为 ``O(h)``。极端哈希冲突下的严格最坏时间取决于
容器实现。返回的新树本身包含 ``n`` 个节点,不计入工作空间。