企业官网建设流程全解析

【题目来源】
https://www.acwing.com/problem/content/3543/

【题目描述】
输入一系列整数，利用所给数据建立一个二叉搜索树，并输出其前序、中序和后序遍历序列。

【输入格式】
第一行一个整数 n，表示输入整数数量。
第二行包含 n 个整数。​​​​​​​

【输出格式】
共三行，第一行输出前序遍历序列，第二行输出中序遍历序列，第三行输出后序遍历序列。
输入中可能有重复元素，但是输出的二叉树遍历序列中重复元素不用输出。

【输入样例】
5
1 6 5 9 8​​​​​​​

【输出样例】
1 6 5 9 8
1 5 6 8 9
5 8 9 6 1

【数据范围】
1≤n≤100,
输入元素取值范围 [1,1000]。

【算法分析】
题目值域为 [1,1000]，故在代码中设置 N=1e3+5。若设 N=1e2+5，如下代码运行时会出现MLE（内存超限）错误。

【算法代码】

#include <bits/stdc++.h> using namespace std; const int N=1e3+5; int le[N],ri[N]; void buildTree(int rt,int val) { /*Equal values are skipped, duplicates are removed.*/ if(rt>val) { if(le[rt]) buildTree(le[rt],val); else le[rt]=val; } else if(rt<val) { if(ri[rt]) buildTree(ri[rt],val); else ri[rt]=val; } } void pre(int rt) { cout<<rt<<" "; if(le[rt]) pre(le[rt]); if(ri[rt]) pre(ri[rt]); } void in(int rt) { if(le[rt]) in(le[rt]); cout<<rt<<" "; if(ri[rt]) in(ri[rt]); } void post(int rt) { if(le[rt]) post(le[rt]); if(ri[rt]) post(ri[rt]); cout<<rt<<" "; } int main() { int n,x,root; cin>>n>>root; for(int i=2; i<=n; i++) { cin>>x; buildTree(root,x); } pre(root),cout<<endl; in(root),cout<<endl; 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/140231285
https://blog.csdn.net/hnjzsyjyj/article/details/120397275
https://www.acwing.com/solution/content/125160/