这题很久之前敲过一次，现在话一1个小时又敲了一次，感觉还是这次的代码简洁优美。
之前的代码：
#include<stdio.h>
#include<stdlib.h>
typedef struct Node{
int value;
struct Node* left;
struct Node* right;
}Node;
int num[1008];
int flag;
void BuildBST(Node* node,int start,int end){
if(flag==0) return;
int middle=start+1;
while(num[middle]<num[start]&&middle<end){
middle++;
}
int tmp=middle;
while(num[middle]>=num[start]&&middle<end){
middle++;
}
if(middle!=end){
flag=0;
node->left=NULL;
node->right=NULL;
return;
}
node->value=num[start];
if(tmp==start+1){
node->left=NULL;
}
else{
node->left=(Node*)malloc(sizeof(Node));
BuildBST(node->left,start+1,tmp);
}
if(tmp==end){
node->right=NULL;
}
else{
node->right=(Node*)malloc(sizeof(Node));
BuildBST(node->right,tmp,end);
}
}
void BuildMirrorBST(Node* node,int start,int end){
if(flag==0) return;
int middle=start+1;
while(num[middle]>=num[start]&&middle<end){
middle++;
}
int tmp=middle;
while(num[middle]<num[start]&&middle<end){
middle++;
}
if(middle!=end){
flag=0;
node->left=NULL;
node->right=NULL;
return;
}
node->value=num[start];
if(tmp==start+1){
node->left=NULL;
}
else{
node->left=(Node*)malloc(sizeof(Node));
BuildMirrorBST(node->left,start+1,tmp);
}
if(tmp==end){
node->right=NULL;
}
else{
node->right=(Node*)malloc(sizeof(Node));
BuildMirrorBST(node->right,tmp,end);
}
}
void PrintPostorderTree(Node* node){
if(node==NULL) return;
PrintPostorderTree(node->left);
PrintPostorderTree(node->right);
printf("%d ",node->value);
}
void PrintPostorderRoot(Node* root){
PrintPostorderTree(root->left);
PrintPostorderTree(root->right);
printf("%d\n",root->value);
}
void dealloc(Node* node){
if(node==NULL) return;
dealloc(node->left);
dealloc(node->right);
free(node);
}
int main(){
int i,n;
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d",&num[i]);
}
flag=1;
Node* root=(Node*)malloc(sizeof(Node));
BuildBST(root,0,n);
if(flag){
printf("YES\n");
PrintPostorderRoot(root);
dealloc(root);
}
else{
flag=1;
dealloc(root->left);
dealloc(root->right);
BuildMirrorBST(root,0,n);
if(flag){
printf("YES\n");
PrintPostorderRoot(root);
}
else{
printf("NO\n");
}
dealloc(root);
}
return 0;
}
这次的代码，还是这次的建树方法好：
#include<stdio.h>
#include<stdlib.h>
int arr[1005],flag;
typedef struct NodeTpye{
int value;
struct NodeTpye* left;
struct NodeTpye* right;
}Node;
Node* buildBST(int s,int e){
int i,j;
if(s>e) return NULL;
for(i=s+1;i<=e;i++){
if(arr[i]>=arr[s]){
break;
}
}
for(j=i+1;j<=e;j++){
if(arr[j]<arr[s]){
flag=0;
return NULL;
}
}
Node* node=(Node*)malloc(sizeof(Node));
node->value=arr[s];
node->left=buildBST(s+1,i-1);
node->right=buildBST(i,e);
return node;
}
Node* buildMirrorBST(int s,int e){
int i,j;
if(s>e) return NULL;
for(i=s+1;i<=e;i++){
if(arr[i]<arr[s]){
break;
}
}
for(j=i+1;j<=e;j++){
if(arr[j]>=arr[s]){
flag=0;
return NULL;
}
}
Node* node=(Node*)malloc(sizeof(Node));
node->value=arr[s];
node->left=buildMirrorBST(s+1,i-1);
node->right=buildMirrorBST(i,e);
return node;
}
void printPostorderTree(Node* node){
if(node==NULL) return;
printPostorderTree(node->left);
printPostorderTree(node->right);
printf("%d ",node->value);
}
void delloc(Node* node){
if(node==NULL) return;
delloc(node->left);
delloc(node->right);
free(node);
}
int main(){
int i,n;
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d",&arr[i]);
}
flag=1;
Node* root=buildBST(0,n-1);
if(flag){
printf("YES\n");
printPostorderTree(root->left);
printPostorderTree(root->right);
printf("%d\n",root->value);
delloc(root);
}
else{
delloc(root);
flag=1;
Node* root=buildMirrorBST(0,n-1);
if(flag){
printf("YES\n");
printPostorderTree(root->left);
printPostorderTree(root->right);
printf("%d\n",root->value);
delloc(root);
}
else{
printf("NO\n");
delloc(root);
}
}
return 0;
}