https://pintia.cn/problem-sets/994805342720868352/problems/994805440976633856
题意：给你一组前序遍历的结果，看是否能建成二叉搜索树或其镜像，若是则输出后序遍历输出。
思路：首先注意这个二叉排序树大于等于为右子树，小于为左子树。然后由于我们已知二叉排序树中序序列(升序)，故只需要知道前序序列即可建树。不过这题还要判断前序序列是否合法，判断标准就是把前序序列拆成根、左子树、右子树，之后判断右子树中是否有非法元素(即左子树中的元素)，然后不断递归即可判断。因为还要判断镜像，所以每种函数也要弄个镜像。
总体来说这题考查对前序序列的理解。
#include <cstdio> #include <iostream> #include <algorithm> #include <string> #include <cstring> #include <vector> #include <stack> #include <queue> #include <cmath> #include <climits> using namespace std; const int MAXN = 1005; const int INF = INT_MAX; struct Treenode{ int data; Treenode* leftchild; Treenode* rightchild; Treenode(int d) : data(d), leftchild(NULL), rightchild(NULL) {} }; int seq[MAXN], N; bool check1(int start, int end, int x){ if(start > end) return true; int i, j; for(i = start; i <= end; i++){ if(seq[i] >= x) break; } for(j = i; j <= end; j++){ if(seq[j] < x) break; } if(j != (end + 1)) return false; if(check1(start + 1, i - 1, seq[start]) == true && check1(i + 1, end, seq[i]) == true) return true; else return false; } bool check2(int start, int end, int x){ if(start > end) return true; int i, j; for(i = start; i <= end; i++){ if(seq[i] < x) break; } //printf("....%d\n", i); for(j = i; j <= end; j++){ if(seq[j] >= x) break; } //printf("....%d\n", j); if(j != (end + 1)) return false; if(check2(start + 1, i - 1, seq[start]) == true && check2(i + 1, end, seq[i]) == true) return true; else return false; } Treenode* Insert1(Treenode* root, int value){ if(root == NULL){ root = new Treenode(value); return root; } if(value < root->data) root->leftchild = Insert1(root->leftchild, value); if(value >= root->data) root->rightchild = Insert1(root->rightchild, value); return root; } Treenode* Insert2(Treenode* root, int value){ if(root == NULL){ root = new Treenode(value); return root; } if(value >= root->data) root->leftchild = Insert2(root->leftchild, value); if(value < root->data) root->rightchild = Insert2(root->rightchild, value); return root; } void PreOrder(Treenode* root, bool &flag){ if(root == NULL) return; PreOrder(root->leftchild, flag); PreOrder(root->rightchild, flag); if(flag) printf(" "); flag = true; printf("%d", root->data); return; } int main(){ // freopen("in.txt", "r", stdin); while(~scanf("%d", &N)){ int kind;//1为正常树，2为镜像树 for(int i = 0; i < N; i++){ scanf("%d", &seq[i]); } if(seq[1] < seq[0]) kind = 1; else kind = 2; if(kind == 1){ if(check1(1, N - 1, seq[0])) printf("YES\n"); else{ printf("NO\n"); continue; } Treenode* root = NULL; for(int j = 0; j < N; j++){ root = Insert1(root, seq[j]); } bool flag = false; PreOrder(root, flag); printf("\n"); } else if(kind == 2){ if(check2(1, N - 1, seq[0])) printf("YES\n"); else{ printf("NO\n"); continue; } Treenode* root = NULL; for(int j = 0; j < N; j++){ root = Insert2(root, seq[j]); } bool flag = false; PreOrder(root, flag); printf("\n"); } } return 0; }
