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

下面分块解释。

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;
    }
};