PTA：后序和中序构造二叉树

二叉树"/>

PTA：后序和中序构造二叉树

后序和中序构造二叉树

• 题目
• • 输入格式
  • 输出格式
  • 输入样例（及其对应的二叉树）
• 代码

题目

本题目要求用后序序列和中序序列构造一棵二叉树（树中结点个数不超过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;
}