PAT 甲级 A1043 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

题意：给出n个要插入的结点的权重，建立二叉查找树，如果插入序列和该二叉查找树的先序遍历序列一致或者和该二叉查找树的镜面树（左子树都是大于或者等于根节点，右子树都是小于根结点的树）的先序遍历序列一致就输出YES，并输出该树的后序遍历序列，否则输出NO；

思路：思路很清晰了，先建立二叉查找树，并保存其插入序列，然后就对该二叉树进行求先序遍历序列和后序遍历序列，也对镜面二叉查找树作相同操作（因为没有建立镜面二叉查找树，根据镜面二叉树的性质更改遍历条件即可），先序遍历和插入序列对比，对就输出后序序列反之输出NO。

代码：
 

#include<iostream>
#include<vector>
using namespace std;
int n,weight;
vector<int > oripre,pre,oripost,post,origin;
struct node{
	int data;
	node* lchild;//指针定义不能单单用逗号隔开用来定义多个指针如node*  
	node* rchild;
};
void insert(node* &root,int x){//插入并建立二叉查找树,记得使用&; 
	if(root==NULL){//递归边界; 
		root=new node;//是root=new node而不是node* root=new node,root已经定义过了不能重新定义，不然会覆盖原来root指针; 
		root->data=x;
		root->lchild=NULL;
		root->rchild=NULL;
		return ;
	}else if(x>=root->data){//一般等于是插左边的，但是题目规定插右边，插左边和插右边的先序遍历结果是不一样的，注意这一点； 
		insert(root->rchild,x);//递归式; 
	}else{
		insert(root->lchild,x);
	} 
}

void oripreorder(node*  root,vector<int > &vi){//二叉查找树的遍历，传入函数的只是副本，要对数组值进行操作就需要&; 
	if(root==NULL)return ;
	vi.push_back(root->data);
	oripreorder(root->lchild,vi);
	oripreorder(root->rchild,vi); 
}

void preorder(node* root,vector<int > &vi){//镜面二叉查找树的先序遍历，还是用原来的那个平衡二叉树，遍历顺序变成根右左就好了; 
	if(root==NULL)return ;
	vi.push_back(root->data);
	preorder(root->rchild,vi);
	preorder(root->lchild,vi);
}

void oripostorder(node* root,vector<int > &vi){//原二叉查找树的后序遍历； 
	if(root==NULL)return ;
	oripostorder(root->lchild,vi);
	oripostorder(root->rchild,vi);
	vi.push_back(root->data);
} 

void postorder(node* root,vector<int > &vi){
	if(root==NULL)return ;
	postorder(root->rchild,vi);
	postorder(root->lchild,vi);
	vi.push_back(root->data);
} 


int main( ){
	scanf("%d",&n);
	node* root=new node;
	root=NULL;
	for(int i=0;i<n;i++){
		scanf("%d",&weight);
		origin.push_back(weight);
		insert(root,weight);//都是从根节点出发，找到查找失败的结点就是要插入的地方; 
	}
	//建立好了二叉查找树; 
	oripreorder(root,oripre);//求二叉查找树的先序遍历;
	
	preorder(root,pre);//镜像二叉查找树的先序遍历,用同一棵树遍历的方式不同；

	if(oripre==origin){//二叉查找树的插入顺序等于二叉查找树的先序遍历； 
		printf("YES\n");
		oripostorder(root,oripost); 
		for(int i=0;i<oripost.size();i++){
			printf("%d",oripost[i]);
			if(i!=oripost.size()-1)printf(" ");
			}
		}else if(pre==origin){//镜像二叉查找树的先序遍历序列等于插入序列;
			printf("YES\n");
			postorder(root,post); 
			for(int i=0;i<post.size();i++){
			printf("%d",post[i]);
			if(i!=post.size()-1)printf(" ");
		}		
	}else {
		printf("NO");
	}
	return 0; 	
}

注意：
 

1.

一般是左子树的值小于或者等于根节点的值，右子树大于根节点的值，但是题目有要求就按照题目要求建树，因为等于的结点在左边和在右边其遍历出来的序列是不一样的，如插入序列为

8 6 7 5 10 8 11的二叉查找树，如果是等于在左边则先序遍历序列为：8 6 5 7 8 10 11

如果等于在右子树则先序遍历序列为：8 6 7 5 10 8 11，所以要看好题目要求。

2.

传入函数的是数组的副本，用完即销毁，在函数内对该副本进行操作不会对原数组造成影响，因此要想在函数改变数组值，需要用引用，传入该数组的地址，直接对该数组进行操作；

3.

二叉查找树的插入是对整个二叉树的结构造成影响，即子结点的建立会改变递归上一层的父节点的child指向，因此root需要用到引用，使得子结点建立后并更新父节点的指向。

4.

两个vector可以直接赋值和比较是否相等，不需要要像一般数组一样需要用循环赋值，比较，将vector成变量就好了，变量可以直接赋值和比较。