从前序和中序遍历重建二叉树：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; 中序区间为空，对应的子树为空。
  2. 取当前根：int val = preorder[preIndex++];
  3. 找到根在中序中的位置：int mid = pos[val];
  4. 构造当前根节点：TreeNode* root = new TreeNode(val);
  5. 递归构造左子树：root->left = self(self, l, mid - 1);
  6. 递归构造右子树：root->right = self(self, mid + 1, r);
  7. 返回当前根：return root;

这种写法相当于在 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，也可以写成比较传统的写法，把 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;
    }
};