【PAT（甲级）】1043 Is It a Binary Search Tree

A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than or equal to the node's key.
• Both the left and right subtrees must also be binary search trees.

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 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

解题思路：

二叉搜索树符合以下三点：

• 所有左子树的节点都小于根节点
• 所有右子树的节点都大于等于根节点
• 左右子树都符合二叉搜索树的条件

镜像先序就是：根，右子树，左子树；

镜像后序就是：右子树，左子树，根；

先序就是：根，左子树，右子树；

后序就是：左子树，右子树，根。

题目给出树的先序输出或者是镜像先序输出，如果不是则输出NO，是的话就输出YES以及对应的后序输出。首先我们构造一棵树，然后用四个相应的数组来存储先序，镜像先序，后序，镜像后序的顺序来读取的这棵树。如果与输入的数组顺序相符合，就可以输出对应的后序了。

易错点：

1. 右子树大于等于根节点；

2. 关于建树的一些问题，指针啥的。

代码：

#include
using namespace std;
 
typedef struct Tree{
	int node;
	Tree *left;
	Tree *right;
};
 
int N;	
vector<int> t,pre,mpre,post,mpost;
void read(Tree* &a,int b){//读取数据来建树 
	if(a == NULL){
		a = new Tree;
		a->node = b;
		a->left = NULL;
		a->right = NULL;
		return;
	}
	else if(b>=a->node){
		read(a->right,b);
	}
	else{
		read(a->left,b);
	}
}
 
void preorder(Tree *a){
	if(a!=NULL){
		pre.push_back(a->node);
		preorder(a->left);
		preorder(a->right);
	}
}
 
void mpreorder(Tree *a){
	if(a != NULL){
		mpre.push_back(a->node);
		mpreorder(a->right);
		mpreorder(a->left);
	}
}
 
void postorder(Tree *a){
	if(a!=NULL){
		postorder(a->left);
		postorder(a->right);
		post.push_back(a->node);
	}
}
 
void mpostorder(Tree *a){
	if(a!=NULL){
		mpostorder(a->right);
		mpostorder(a->left);
		mpost.push_back(a->node);
	}
}
int main(){
	Tree *tree = NULL;
	cin>>N;
	for(int i=0;i
		int x;
		cin>>x;
		t.push_back(x);
		read(tree,x);
	}
	
	preorder(tree);
	mpreorder(tree);
	postorder(tree);
	mpostorder(tree);
 
	if(t == pre){
		cout<<"YES"<
		for(auto i=post.begin();i!=post.end();i++){
			if(i==post.begin())
				cout<<*i;
			else 
				cout<<" "<<*i;
		}
	}
	else if(t == mpre){
		cout<<"YES"<
		for(auto i=mpost.begin();i!=mpost.end();i++){
			if(i==mpost.begin())
				cout<<*i;
			else 
				cout<<" "<<*i;
		}
	}
	else{
		cout<<"NO";
	}
	return 0;
}