编辑代码

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

// 定义树节点结构
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 构建二叉树的辅助函数
TreeNode* buildTreeHelper(vector<int>& preorder, int preStart, int preEnd, 
                          vector<int>& inorder, int inStart, int inEnd,
                          unordered_map<int, int>& inorderIndexMap) {
    if (preStart > preEnd || inStart > inEnd) {
        return nullptr;
    }

    int rootVal = preorder[preStart];
    TreeNode* root = new TreeNode(rootVal);

    int inorderIndex = inorderIndexMap[rootVal];
    int leftTreeSize = inorderIndex - inStart;

    root->left = buildTreeHelper(preorder, preStart + 1, preStart + leftTreeSize, 
                                 inorder, inStart, inorderIndex - 1, inorderIndexMap);

    root->right = buildTreeHelper(preorder, preStart + leftTreeSize + 1, preEnd, 
                                  inorder, inorderIndex + 1, inEnd, inorderIndexMap);
    
    return root;
}

// 主函数
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    unordered_map<int, int> inorderIndexMap;
    for (int i = 0; i < inorder.size(); i++) {
        inorderIndexMap[inorder[i]] = i;
    }
    return buildTreeHelper(preorder, 0, preorder.size() - 1, 
                           inorder, 0, inorder.size() - 1, inorderIndexMap);
}

// 打印树的辅助函数
void printTree(TreeNode* root) {
    if (!root) return;
    cout << root->val << " ";
    printTree(root->left);
    printTree(root->right);
}

int main() {
    vector<int> preorder = {3, 9, 20, 15, 7};
    vector<int> inorder = {9, 3, 15, 20, 7};
    
    TreeNode* root = buildTree(preorder, inorder);
    
    cout << "Preorder of constructed tree: ";
    printTree(root);
    
    return 0;
}