PAT 甲级 1043 Is It a Binary Search Tree
https://pintia.cn/problem-sets/994805342720868352/problems/994805440976633856 ? A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:
If we swap the left and right subtrees of every node,then the resulting tree is called the?Mirror Image?of a BST. Now given a sequence of integer keys,you are supposed to tell if it is the preorder traversal sequence of a BST or the mirror image of a BST. Input Specification:Each input file contains one test case. For each case,the first line contains a positive integer?N?(≤1000). Then?N?integer keys are given in the next line. All the numbers in a line are separated by a space. Output Specification:For each test case,first print in a line? Sample Input 1:7 8 6 5 7 10 8 11 Sample Output 1:YES 5 7 6 8 11 10 8 Sample Input 2:7 8 10 11 8 6 7 5 Sample Output 2:YES 11 8 10 7 5 6 8 Sample Input 3:7 8 6 8 5 10 9 11 Sample Output 3:NO
?
代码: #include <bits/stdc++.h> using namespace std; int N; vector<int> pre,post; bool isMirror; void solve(int root,int point) { if(root > point) return ; int i = root + 1,j = point; if(!isMirror) { while(i <= point && pre[root] > pre[i]) i ++; while(j > root && pre[root] <= pre[i]) j --; } else { while(i <= point && pre[root] <= pre[i]) i ++; while(j > root && pre[root] > pre[j]) j --; } if(i - j != 1) return ; solve(root + 1,j); solve(i,point); post.push_back(pre[root]); } int main() { scanf("%d",&N); pre.resize(N); for(int i = 0; i < N; i ++) scanf("%d",&pre[i]); solve(0,N - 1); if(post.size() != N) { isMirror = true; post.clear(); solve(0,N - 1); } if(post.size() == N) { printf("YESn"); z for(int i = 0; i < N; i ++) { printf("%d",post[i]); printf("%s",i != N - 1 ? " " : "n"); } } else printf("NOn"); return 0; } 先假设不是镜面的树 按照二叉搜索树的性质进行查找 并且按照后序遍历存起来 如果后序遍历存起来之后不是 N 个 则 isMirror = true 反着再查一遍 如果反过来查一遍之后 post.size() = N 的话说明是镜面的 如果还不是的话就是 NO 然后输出 期末被高数折磨的死去活来 好多天没摸键盘了 手好生 哭唧唧 今天想学学建树 期末期末快过去吧!!!? FH(强行提到 FH) (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |