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:7 8 6 5 7 10 8 11Sample Output 1:
YES 5 7 6 8 11 10 8Sample Input 2:
7 8 10 11 8 6 7 5Sample Output 2:
YES 11 8 10 7 5 6 8Sample Input 3:
7 8 6 8 5 10 9 11Sample Output 3:
NO
#include<cstdio> #include<cstdlib> #define MAX 1005 using namespace std; typedef struct Node { int data; Node *left; Node *right; }Node; int Keys[MAX]; int PreOrder[MAX]; int PreOrderImg[MAX]; int PostOrder[MAX]; int index=0; void InsertNode(Node **root,int key,bool Img) { if(*root==NULL) { *root=(Node *)malloc(sizeof(Node)); if(!(*root)) { printf("No enough memory!\n"); exit(-1); } (*root)->left=NULL; (*root)->right=NULL; (*root)->data=key; return; } else { if(Img) { if((*root)->data<=key) InsertNode(&((*root)->left),key,Img); else InsertNode(&((*root)->right),key,Img); } else { if((*root)->data>key) InsertNode(&((*root)->left),key,Img); else InsertNode(&((*root)->right),key,Img); } } } void CreateBSTree(Node **root,int keys[],int len,bool Img) { for(int i=0;i<len;i++) InsertNode(root,keys[i],Img); } void PreOrderTraverse(Node *root,bool Img) { if(root==NULL) return ; if(Img) PreOrderImg[index++]=root->data; else PreOrder[index++]=root->data; if(root->left) PreOrderTraverse(root->left,Img); if(root->right) PreOrderTraverse(root->right,Img); } bool IsSame(int keys[],int len,bool Img) { int i; if(Img) { for(i=0;i<len;i++) { if(keys[i]!=PreOrderImg[i]) return false; } return true; } else { for(i=0;i<len;i++) { if(keys[i]!=PreOrder[i]) return false; } return true; } } void PostOrderTraverse(Node *root) { if(root==NULL) return; if(root->left) PostOrderTraverse(root->left); if(root->right) PostOrderTraverse(root->right); PostOrder[index++]=root->data; } void Display(int len) { int i; for(i=0;i<len;i++) { if(i==0) printf("%d",PostOrder[i]); else printf(" %d",PostOrder[i]); } printf("\n"); } void Destroy(Node **root) { if((*root)->left==NULL&&(*root)->right==NULL) { free(*root); *root=NULL; } else if((*root)->left) Destroy(&((*root)->left)); else if((*root)->right) Destroy(&((*root)->right)); } int main(int argc,char *argv[]) { int i,n; Node *root=NULL;//这两个初始化必须得有,否则会出现段错误;在自己的机器 Node *rootImg=NULL; //上可以运行,但提交后就段错误,估计是服务器端 scanf("%d",&n); //编译器的问题吧 for(i=0;i<n;i++) scanf("%d",&Keys[i]); CreateBSTree(&root,Keys,n,false); CreateBSTree(&rootImg,Keys,n,true); index=0; PreOrderTraverse(root,false); if(IsSame(Keys,n,false)) { printf("YES\n"); index=0; PostOrderTraverse(root); Display(n); } else { index=0; PreOrderTraverse(rootImg,true); if(IsSame(Keys,n,true)) { printf("YES\n"); index=0; PostOrderTraverse(rootImg); Display(n); } else { printf("NO\n"); } } Destroy(&root); Destroy(&rootImg); return 0; }
Pat(Advanced Level)Practice--1043(Is It a Binary Search Tree),布布扣,bubuko.com
Pat(Advanced Level)Practice--1043(Is It a Binary Search Tree)
原文:http://blog.csdn.net/cstopcoder/article/details/25752371