本文共 3070 字,大约阅读时间需要 10 分钟。
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 "YES" if the sequence is the preorder traversal sequence of a BST or the mirror image of a BST, or "NO" if not. Then if the answer is "YES", print in the next line the postorder traversal sequence of that tree. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.
Sample Input 1:78 6 5 7 10 8 11Sample Output 1:
YES5 7 6 8 11 10 8Sample Input 2:
78 10 11 8 6 7 5Sample Output 2:
YES11 8 10 7 5 6 8Sample Input 3:
78 6 8 5 10 9 11Sample Output 3:
NO
#include#include #include #include #include #include #include using namespace std;struct Node{ int data; Node * left; Node * right; Node():data(0),left(NULL),right(NULL) {}; Node(int x):data(x),left(NULL),right(NULL) {};};void Post(Node *T,vector * o){ if(!T) return ; if(T->left) Post(T->left,o); if(T->right) Post(T->right,o); (*o).push_back(T->data);}vector nums;Node *bstCreate(int sstart,int eend,bool *flag){ if(sstart>eend) return NULL; else { Node *T = new Node(nums[sstart]); int i = sstart+1; while(i<=eend&&nums[i] =nums[sstart]) j++; if(i!=eend+1&&j!=eend+1) { *flag = false; return NULL; } T->left = bstCreate(sstart+1,i-1,flag); T->right = bstCreate(i,eend,flag); return T; }}Node *MirrorCreate(int sstart,int eend,bool *flag){ if(sstart>eend) return NULL; else { Node *T = new Node(nums[sstart]); int i = sstart+1; while(i<=eend&&nums[i]>=nums[sstart]) i++; int j = i; while(j<=eend&&nums[j] left = MirrorCreate(sstart+1,i-1,flag); T->right = MirrorCreate(i,eend,flag); return T; }}int main(){ int n,temp; Node *root=NULL; scanf("%d",&n); for(int i=0; i
转载地址:http://xmhji.baihongyu.com/