AcWing 3540：二叉搜索树 ← BST

【题目来源】https://www.acwing.com/problem/content/3543/【题目描述】输入一系列整数利用所给数据建立一个二叉搜索树并输出其前序、中序和后序遍历序列。【输入格式】第一行一个整数 n表示输入整数数量。第二行包含 n 个整数。​​​​​​​【输出格式】共三行第一行输出前序遍历序列第二行输出中序遍历序列第三行输出后序遍历序列。输入中可能有重复元素但是输出的二叉树遍历序列中重复元素不用输出。【输入样例】51 6 5 9 8​​​​​​​【输出样例】1 6 5 9 81 5 6 8 95 8 9 6 1【数据范围】1≤n≤100,输入元素取值范围 [1,1000]。【算法分析】题目值域为 [1,1000]故在代码中设置 N1e35。若设 N1e25如下代码运行时会出现MLE内存超限错误。【算法代码】#include bits/stdc.h using namespace std; const int N1e35; int le[N],ri[N]; void buildTree(int rt,int val) { /*Equal values are skipped, duplicates are removed.*/ if(rtval) { if(le[rt]) buildTree(le[rt],val); else le[rt]val; } else if(rtval) { if(ri[rt]) buildTree(ri[rt],val); else ri[rt]val; } } void pre(int rt) { coutrt ; if(le[rt]) pre(le[rt]); if(ri[rt]) pre(ri[rt]); } void in(int rt) { if(le[rt]) in(le[rt]); coutrt ; if(ri[rt]) in(ri[rt]); } void post(int rt) { if(le[rt]) post(le[rt]); if(ri[rt]) post(ri[rt]); coutrt ; } int main() { int n,x,root; cinnroot; for(int i2; in; i) { cinx; buildTree(root,x); } pre(root),coutendl; in(root),coutendl; post(root); return 0; } /* in: 5 1 6 5 9 8 out: 1 6 5 9 8 1 5 6 8 9 5 8 9 6 1 */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/140231285https://blog.csdn.net/hnjzsyjyj/article/details/120397275https://www.acwing.com/solution/content/125160/