数据结构相关问题通过直接结题

Question

第二道题希望详细的内容，我不太懂，如果能运行直接结题，看看我的通过率，希望各位能快点

Answer 1

来 给你

#include <iostream>
#include <vector>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

TreeNode* buildTree(std::vector<int>& inorder, std::vector<int>& postorder, int inStart, int inEnd, int postStart, int postEnd) {
    if (inStart > inEnd || postStart > postEnd) {
        return nullptr;
    }

    int rootVal = postorder[postEnd];
    TreeNode* root = new TreeNode(rootVal);

    int rootIndex = 0;
    for (int i = inStart; i <= inEnd; ++i) {
        if (inorder[i] == rootVal) {
            rootIndex = i;
            break;
        }
    }

    int leftSubtreeSize = rootIndex - inStart;

    root->left = buildTree(inorder, postorder, inStart, rootIndex - 1, postStart, postStart + leftSubtreeSize - 1);
    root->right = buildTree(inorder, postorder, rootIndex + 1, inEnd, postStart + leftSubtreeSize, postEnd - 1);

    return root;
}

void postorderTraversal(TreeNode* root) {
    if (root == nullptr) {
        return;
    }

    postorderTraversal(root->left);
    postorderTraversal(root->right);
    std::cout << root->val << " ";
}

void inorderTraversal(TreeNode* root) {
    if (root == nullptr) {
        return;
    }

    inorderTraversal(root->left);
    std::cout << root->val << " ";
    inorderTraversal(root->right);
}

int main() {
    std::vector<int> inorder = {4, 2, 8, 5, 1, 6, 9, 3, 7};
    std::vector<int> postorder = {4, 8, 5, 2, 9, 6, 7, 3, 1};

    int n = inorder.size();
    TreeNode* root = buildTree(inorder, postorder, 0, n - 1, 0, n - 1);

    std::cout << "后序遍历结果：";
    postorderTraversal(root);
    std::cout << std::endl;

    std::cout << "中序遍历结果：";
    inorderTraversal(root);
    std::cout << std::endl;

    return 0;
}