从前序和中序遍历重建二叉树 —— C++ 递归 + 哈希表写法解析

从前序和中序遍历重建二叉树 —— C++ 递归 + 哈希表写法解析

一、题目背景

已知一棵二叉树的：

• 前序遍历序列preorder
• 中序遍历序列inorder

并且树中不存在重复节点值，要求 重建这棵二叉树，返回根节点 TreeNode*。

二、关键性质回顾

二叉树的遍历有这些性质（这里用到前序 + 中序）：

1. 前序遍历（Preorder）：
   顺序是：根节点 -> 左子树 -> 右子树
    所以 preorder[0] 一定是整棵树的 根节点。
2. 中序遍历（Inorder）：
   顺序是：左子树 -> 根节点 -> 右子树
   在中序序列中，根节点左边的部分是“左子树”，右边的部分是“右子树”。

因为题目保证所有节点值互不相同，所以我们可以用一个哈希表

unordered_map<int, int> pos; 

来把「节点值」映射到「它在中序遍历中的下标」，方便 O(1) 查找。

三、整体思路

1. 预处理：
   把 inorder 每个值所在的位置存进哈希表 pos，方便通过值快速找到它在中序序列中的下标。
2. 前序的指针 preIndex：
   因为前序遍历顺序是：根 → 左 → 右，我们可以维护一个全局下标 preIndex，每次从 preorder[preIndex] 取当前子树的根，然后 preIndex++，继续构造子树。
   • 如果 l > r，说明这个区间是空的，对应的子树为空，返回 nullptr。
   • 否则：
     1. 取当前根：val = preorder[preIndex++]
     2. 在中序中找到根的位置：mid = pos[val]
     3. 左子树对应中序区间 [l, mid - 1]
     4. 右子树对应中序区间 [mid + 1, r]
     5. 递归生成左右子树，并挂到根上。

递归构造子树：
用一个函数 dfs(l, r) 表示：

根据「中序遍历的区间 [l, r]」，构造出这一段对应的子树，并返回这棵子树的根节点指针。

四、代码实现解析

代码如下：

class Solution { public: TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { int n = preorder.size(); unordered_map<int,int> pos; pos.reserve(n * 2); for (int i = 0; i < n; ++i) pos[inorder[i]] = i; int preIndex = 0; auto dfs = [&](auto&& self, int l, int r) -> TreeNode* { if (l > r) return nullptr; int val = preorder[preIndex++]; int mid = pos[val]; TreeNode* root = new TreeNode(val); root->left = self(self, l, mid - 1); root->right = self(self, mid + 1, r); return root; }; return dfs(dfs, 0, n - 1); } }; 

下面分块解释。

1. 建立中序下标哈希表

int n = preorder.size(); unordered_map<int,int> pos; pos.reserve(n * 2); for (int i = 0; i < n; ++i) pos[inorder[i]] = i; 

• pos 的作用：
  pos[x] 表示「值为 x 的节点，在中序遍历中的位置」。
• reserve(n * 2);：
  提前为哈希表预留空间，减少扩容，略微优化性能。

2. 维护前序下标

int preIndex = 0; 

• preIndex 表示当前该从 preorder 的哪个位置取根节点。
• 每次 preorder[preIndex++]，就像顺着前序遍历顺序不断往前走。

3. 用 lambda + Y 组合做递归

auto dfs = [&](auto&& self, int l, int r) -> TreeNode* { if (l > r) return nullptr; int val = preorder[preIndex++]; int mid = pos[val]; TreeNode* root = new TreeNode(val); root->left = self(self, l, mid - 1); root->right = self(self, mid + 1, r); return root; }; 

• 这里 dfs 是一个 泛型 lambda，通过参数 self 自己调用自己，实现递归。
• 参数含义：
  • self：指向自身的可调用对象，用于递归调用。
  • l, r：当前子树对应的 中序遍历区间[l, r]。
• 递归逻辑：
  1. 边界：if (l > r) return nullptr;
     中序区间为空，对应的子树为空。

返回当前根：

return root; 

递归构造右子树：

root->right = self(self, mid + 1, r); 

递归构造左子树：

root->left = self(self, l, mid - 1); 

构造当前根节点：

TreeNode* root = new TreeNode(val); 

找到根在中序中的位置：

int mid = pos[val]; 

取当前根：

int val = preorder[preIndex++]; 

这种写法相当于在 buildTree 函数内部，临时定义了一个递归函数，而不需要单独写成类的成员函数。

4. 调用入口

return dfs(dfs, 0, n - 1); 

• 一开始整棵树对应的 中序区间 就是 [0, n - 1]。
• 把 dfs 自己作为第一个参数传进去，用来实现递归。

五、复杂度分析

• 时间复杂度：
  • 建哈希表：O(n)
  • 每个节点在递归中只被处理一次、查哈希表一次：O(1)
     总时间复杂度：O(n)
• 空间复杂度：
  • 哈希表 pos 使用 O(n) 空间
  • 递归栈最坏情况（退化成链表）深度为 O(n)
     总空间复杂度：O(n)

六、更传统一点的方式（主要我想多用lambda表达式）

如果不想用 lambda，也可以写成比较传统的写法，把 dfs 写成类的成员函数：

class Solution { public: unordered_map<int, int> pos; vector<int> preorder; int preIndex = 0; TreeNode* buildTree(vector<int>& preorder_, vector<int>& inorder) { preorder = preorder_; int n = preorder.size(); pos.reserve(n * 2); for (int i = 0; i < n; ++i) pos[inorder[i]] = i; return dfs(0, n - 1); } TreeNode* dfs(int l, int r) { if (l > r) return nullptr; int val = preorder[preIndex++]; int mid = pos[val]; TreeNode* root = new TreeNode(val); root->left = dfs(l, mid - 1); root->right = dfs(mid + 1, r); return root; } };