7-42 搜索树判断

7-42 搜索树判断 (25分)

对于二叉搜索树，我们规定任一结点的左子树仅包含严格小于该结点的键值，而其右子树包含大于或等于该结点的键值。如果我们交换每个节点的左子树和右子树，得到的树叫做镜像二叉搜索树。

现在我们给出一个整数键值序列，请编写程序判断该序列是否为某棵二叉搜索树或某镜像二叉搜索树的前序遍历序列，如果是，则输出对应二叉树的后序遍历序列。

输入格式:

输入的第一行包含一个正整数N（≤1000），第二行包含N个整数，为给出的整数键值序列，数字间以空格分隔。

输出格式:

输出的第一行首先给出判断结果，如果输入的序列是某棵二叉搜索树或某镜像二叉搜索树的前序遍历序列，则输出YES，否侧输出NO。如果判断结果是YES，下一行输出对应二叉树的后序遍历序列。数字间以空格分隔，但行尾不能有多余的空格。

输入样例1:

7
8 6 5 7 10 8 11

输出样例1:

YES
5 7 6 8 11 10 8

输入样例2:

7
8 6 8 5 10 9 11

输出样例2:

NO

#include<iostream>
#include<cstdio> 
#include<malloc.h>
using namespace std;

int n;//结点个数 
int a[1010];//输入序列 
int b[1010];//先序序列 

struct node{
	int data;
	node *left;
	node *right;
} *head;//头结点 


void *create(){//建树 
	for(int i=0;i<n;i++){
		node *p=(node *)malloc(sizeof(node));
		p->data=a[i];
		p->left=NULL;
		p->right=NULL;
		if(head==NULL){//确定头结点 
			head=p;
		}
		else{
			node *temp=head;
			while(temp){
				if(p->data<temp->data){//查找左子树 
					if(temp->left==NULL){
						temp->left=p;
						break;
					}
					else{
						temp=temp->left;
					}
				}
				else{//查找右子树 
					if(temp->right==NULL){
						temp->right=p;
						break;
					}
					else{
						temp=temp->right;
					}
				}
			}
		}
	}
}

int x;//记录先序节点顺序 
void preorder(node *p){//输出先序序列 
	if(p!=NULL){
		b[x++]=p->data;//
		preorder(p->left);
		preorder(p->right);
	}
}

bool check(){//检查是否与先序序列相同 
	for(int i=0;i<n;i++){
		if(a[i]!=b[i]){
			return false;
		}
	}
	return true;
}

void swap(node *p){//交换左右节点 
	if(p==NULL){
		return ;
	}
	else{
		node *temp=p->left;
		p->left=p->right;
		p->right=temp;
		swap(p->left);
		swap(p->right);
	}
} 

int f=0;//记录第一个输出 
void suborder(node *p){//后序遍历 
	if(p!=NULL){
		suborder(p->left);
		suborder(p->right);
		if(f) printf(" ");//除第一个输出前没有空格 
		printf("%d",p->data);
		f=1;
	}
}

int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	head=NULL;
	create();
	x=0;
	preorder(head);
	if(check()){
		printf("YES\n");
		suborder(head);
	}
	else{
		swap(head);//镜像二叉树 
		x=0;
		preorder(head);
		if(check()){
			printf("YES\n");
			suborder(head);
		}
		else{
			printf("NO\n");
		}
	}
	return 0;
}