【二叉树】LC 105.从前序与中序遍历序列构造二叉树

文章目录

• 前言
• 一、题目
• • 1、原题链接
  • 2、题目描述
• 二、个人思路整理
• • 1、思路分析
  • 2、解题代码
• 三、知识风暴

前言

本专栏文章为《LeetCode 热题 100》的刷题题解，相关内容如有侵权，立即删除。

一、题目

1、原题链接

105.从前序与中序遍历序列构造二叉树

2、题目描述

二、个人思路整理

1、思路分析

核心是利用前序遍历和中序遍历各自的遍历顺序特点，通过递归分治来确定根节点及其左右子树的范围。 具体步骤：

• 知道了左子树的节点数量 left_size，就可以在前序遍历中切分出对应的区间：
  • 左子树的前序区间：[pre_left + 1, pre_left + left_size]
  • 左子树的中序区间：[in_left, in_root – 1]
  • 右子树的前序区间：[pre_left + left_size + 1, pre_right]
  • 右子树的中序区间：[in_root + 1, in_right]
• 递归构建左、右子树并挂载到根节点上。

2、解题代码

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
private:
// 哈希表：存储中序遍历中 节点值->数组索引 的映射，以实现O(1)快速定位根节点
unordered_map<int, int> in_pos;

/**
* @brief 递归构造二叉树
* @param preorder 前序遍历序列引用
* @param pre_left 当前子树在前序遍历序列中的起始下标
* @param pre_right 当前子树在前序遍历序列中的结束下标
* @param inorder 中序遍历序列引用
* @param in_left 当前子树在中序遍历序列中的起始下标
* @param in_right 当前子树在中序遍历序列中的结束下标
* @return 当前子树的根节点指针
*/
TreeNode* build(const vector<int>& preorder, int pre_left, int pre_right,
const vector<int>& inorder, int in_left, int in_right) {
// 递归终止条件：当前子树的区间为空
if (pre_left > pre_right || in_left > in_right) {
return nullptr;
}

// 1. 前序遍历的第一个节点为当前子树的根节点
int root_val = preorder[pre_left];
TreeNode* root = new TreeNode(root_val);

// 2. 在中序遍历中找到根节点索引
int in_root = in_pos[root_val];
int left_size = in_root – in_left; // 左子树节点数

// 3. 递归构建左右子树
root->left = build(preorder, pre_left + 1, pre_left + left_size, inorder, in_left, in_root – 1);
root->right = build(preorder, pre_left + left_size + 1, pre_right, inorder, in_root + 1, in_right);

return root;
}
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int n = inorder.size();

// 初始化中序遍历的索引映射
for (int i = 0; i < n; i++) {
in_pos[inorder[i]] = i;
}

// 从整棵树的全局区间开始递归构建
return build(preorder, 0, n – 1, inorder, 0, n – 1);
}
};

复杂度分析

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

三、知识风暴

前序遍历（Preorder Traversal） 是本题的核心：从前序与中序遍历序列构造二叉树，本质上就是利用前序遍历确定根节点、中序遍历划分左右子树，通过递归分治重建整棵树。前序遍历的顺序是 根 -> 左 -> 右，中序遍历的顺序是 左 -> 根 -> 右，两者结合即可唯一确定一棵二叉树。

算法核心思想：

• 前序遍历定根：前序遍历的第一个元素必然是当前子树的根节点，这是递归分治的起点。
• 中序遍历划分：在中序遍历中找到根节点的位置后，其左侧即为左子树的中序序列，右侧即为右子树的中序序列，从而确定左右子树的范围。
• 递归分治：根据中序划分出的左右子树节点数量，在前序遍历中切分出对应的左右子树区间，递归构建左右子树并挂载到根节点上。

常见对比：递归 vs 迭代（显式栈）

• 递归（分治）：这是本题最直观的解法，利用递归调用栈天然保存了回溯路径，代码简洁清晰；但空间复杂度为 $O(h)$
• 迭代（显式栈）：用栈模拟递归过程，每次从栈中取出一个节点并处理其左右子树区间，空间复杂度同样为 $O(n)$
• 迭代（哈希表加速）：这是本题的优化关键。预先使用 unordered_map 记录中序遍历中每个值的索引，可在 $O(1)$

哈希表加速思想：

• 核心思想：中序遍历序列中每个节点的值都是唯一的，因此可以预先建立 值 -> 索引 的映射表，在递归过程中直接查表定位根节点，无需每次遍历查找。
• 与本题的联系：本题的递归分治过程中，每次都需要在中序遍历中定位根节点。若不使用哈希表，每次定位耗时 $O(n)$
• 注意事项：哈希表建立的前提是节点值唯一。若题目允许重复值，则需要额外的处理策略（如结合索引范围进一步约束）。

使用要点：

• 区间边界：递归时需同时维护前序和中序的左右边界（pre_left、pre_right、in_left、in_right），确保每次递归只处理当前子树的区间。
• 左子树大小：left_size = in_root – in_left 是划分左右子树的关键，它决定了前序遍历中左右子树区间的切分位置。
• 递归终止：当 pre_left > pre_right 或 in_left > in_right 时，说明当前子树为空，返回 nullptr 作为边界条件的兜底。
• 空树处理：若输入序列为空，直接返回 nullptr，作为边界条件的兜底。

算法变体与扩展：

• 二叉树的中序遍历（LeetCode 94）：理解中序遍历的序列特点是本题划分左右子树的基础。
• 从中序与后序遍历序列构造二叉树（LeetCode 106）：与本题对称，利用后序遍历确定根节点、中序遍历划分左右子树，可对比理解不同遍历组合的重建逻辑。
• 将有序数组转换为二叉搜索树（LeetCode 108）：同样是利用序列划分递归构建二叉树，可对比理解不同数据源下的构建策略。
• 二叉树的层序遍历（LeetCode 102）：与本题的深度优先构建不同，层序遍历采用广度优先，可对比理解树的两种遍历与构建方式。

相关 LeetCode 例题：

• 94. 二叉树的中序遍历（中序遍历序列特点）
• 106. 从中序与后序遍历序列构造二叉树（对称的构建思路）
• 108. 将有序数组转换为二叉搜索树（序列划分递归构建）
• 102. 二叉树的层序遍历（广度优先遍历对比）