做网站 空间,生产模板的厂家,sem推广软件选哪家,wordpress 跳转适配后序和中序构造二叉树 题目输入格式输出格式输入样例#xff08;及其对应的二叉树#xff09; 代码 题目
本题目要求用后序序列和中序序列构造一棵二叉树#xff08;树中结点个数不超过10个#xff09;#xff0c;并输出其先序序列。
输入格式
在第一行中输入元素个数… 后序和中序构造二叉树 题目输入格式输出格式输入样例及其对应的二叉树 代码 题目
本题目要求用后序序列和中序序列构造一棵二叉树树中结点个数不超过10个并输出其先序序列。
输入格式
在第一行中输入元素个数。
第二行中输入后序序列用空格分隔。
第三行中输入中序序列用空格分隔。
输出格式
输出此二叉树的先序序列用空格分隔最后也有一个空格。
输入样例及其对应的二叉树
5
20 40 50 30 10
20 10 40 30 50## 输出样例
10 20 30 40 50 代码
#include iostream
#include vector
#include unordered_mapclass TreeNode {
public:int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};TreeNode* buildTree(std::vectorint inorder, std::vectorint postorder, int inStart, int inEnd, int postStart, int postEnd, std::unordered_mapint, 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::vectorint postorder(n);std::vectorint 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_mapint, 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;
}
