PTA：后序和中序构造二叉树-CSDN博客

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

后序和中序构造二叉树

题目
代码

题目

本题目要求用后序序列和中序序列构造一棵二叉树树中结点个数不超过10个并输出其先序序列。

输入格式

在第一行中输入元素个数。

第二行中输入后序序列用空格分隔。

第三行中输入中序序列用空格分隔。

输出格式

输出此二叉树的先序序列用空格分隔最后也有一个空格。

输入样例及其对应的二叉树

5
20 40 50 30 10
20 10 40 30 50

## 输出样例
10 20 30 40 50

代码

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

class TreeNode {
public:
    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, std::unordered_map<int, int>& indexMap) {
    if (inStart > inEnd || postStart > postEnd) {
        return nullptr;
    }

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

    int leftSubtreeSize = rootIndex - inStart;

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

    return root;
}

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

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

int main() {
    int n;
    std::cin >> n;

    std::vector<int> postorder(n);
    std::vector<int> inorder(n);

    for (int i = 0; i < n; ++i) {
        std::cin >> postorder[i];
    }

    for (int i = 0; i < n; ++i) {
        std::cin >> inorder[i];
    }

    std::unordered_map<int, int> indexMap;
    for (int i = 0; i < n; ++i) {
        indexMap[inorder[i]] = i;
    }

    TreeNode* root = buildTree(inorder, postorder, 0, n - 1, 0, n - 1, indexMap);
    preorderTraversal(root);
    std::cout << std::endl;

    return 0;
}