题解 | 重建二叉树

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
  private:
    unordered_map<int, int> vinIndex; // 中序遍历值到索引的映射

    TreeNode* build(vector<int>& preOrder, int preStart, int preEnd,
                    vector<int>& vinOrder, int vinStart, int vinEnd) {
        if (preStart > preEnd || vinStart > vinEnd) {
            return nullptr;
        }

        // 前序遍历第一个节点是根节点
        int rootVal = preOrder[preStart];
        TreeNode* root = new TreeNode(rootVal);

        // 在中序遍历中找到根节点位置
        int rootIndex = vinIndex[rootVal];
        int leftSize = rootIndex - vinStart; // 左子树节点个数

        // 递归构建左右子树
        root->left = build(preOrder, preStart + 1, preStart + leftSize,
                           vinOrder, vinStart, rootIndex - 1);
        root->right = build(preOrder, preStart + leftSize + 1, preEnd,
                            vinOrder, rootIndex + 1, vinEnd);

        return root;
    }

  public:
    TreeNode* reConstructBinaryTree(vector<int>& preOrder, vector<int>& vinOrder) {
        if (preOrder.empty() || vinOrder.empty() ||
                preOrder.size() != vinOrder.size()) {
            return nullptr;
        }

        // 构建中序遍历的索引映射
        for (int i = 0; i < vinOrder.size(); i++) {
            vinIndex[vinOrder[i]] = i;
        }

        return build(preOrder, 0, preOrder.size() - 1,
                     vinOrder, 0, vinOrder.size() - 1);
    }
};

算法核心
前序遍历确定根节点：前序遍历的第一个元素就是当前子树的根节点
中序遍历划分左右子树：在中序遍历中找到根节点，左边是左子树，右边是右子树
递归构建：分别对左右子树递归执行上述过程

关键参数说明
preStart, preEnd：当前子树在前序遍历中的范围
vinStart, vinEnd：当前子树在中序遍历中的范围
leftSize：左子树的节点个数，用于确定子树范围
vinIndex：哈希表，存储中序遍历值到索引的映射，加速查找

时间复杂度分析
时间复杂度：O(n)
每个节点只处理一次
哈希表查找根节点位置为 O(1)
空间复杂度：O(n)
递归栈深度为树的高度
哈希表存储 n 个元素的映射