1043. Is It a Binary Search Tree (25)

https://www.patest.cn/contests/pat-a-PRactise/1043

//给定一克BST，构建BST，判断给定的序列是否是构建好的这棵BST的前序序列/*	如果是的话 :输出这棵树的后序	。。	或者判断这棵树进行左右子树翻转后，如果这棵BST的前序序列是给定的序列，	输出翻转后的这棵树的后序。*/#include <iostream>#include <vector>using namespace std;struct node {	int data;	node *lchild;	node *rchild;};vector<int> righta,rightb;//前序遍历序列数组vector<int> seq,post;void insert(node *&root, int num) {	if ( root == NULL ) {		root = new node();		root->data = num;		root->lchild = NULL;		root->rchild = NULL;		return;	}	if ( num < root->data) {		insert(root->lchild,num);	}	else {		insert(root->rchild,num);	}} void preOrder(node *root) {	if ( root == NULL ) return;	righta.push_back(root->data);	preOrder(root->lchild);	preOrder(root->rchild);}void ARL(node *root) {	if ( root == NULL ) return;	rightb.push_back(root->data);	ARL(root->rchild);	ARL(root->lchild);}void postOrder(node *root) {	if ( root == NULL ) return;	postOrder(root->lchild);	postOrder(root->rchild);	post.push_back(root->data);}void Print(vector<int> vc) {	vector<int>::iterator it  = vc.begin();	bool flag = true;	for ( ; it != vc.end(); it++) {		if ( flag ) {			printf("%d",(*it));			flag = false;		}else {			printf(" %d",(*it));		}	}	printf("/n");}void Change(node *root) {	if ( root == NULL ) return;	node *temp = root->lchild;	root->lchild = root->rchild;	root->rchild = temp;	Change(root->lchild);	Change(root->rchild);}int main() {	int n,num;	node *root = NULL;	scanf("%d",&n);	for ( int i = 0; i < n; i++ ) {		scanf("%d",&num);		seq.push_back(num);		insert(root,num);	}	preOrder(root);	ARL(root);	if ( righta == seq ) {		printf("YES/n");		post.clear();		postOrder(root);		Print(post);	}else if ( rightb == seq ) {		printf("YES/n");		Change(root);		postOrder(root);		Print(post);	}	else {		printf("NO/n");	}	return 0;}