Pat grade a 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

The question ： give n The weight of the nodes to be inserted , Build a binary search tree , If the insertion sequence is consistent with the preorder traversal sequence of the binary search tree or with the mirror tree of the binary search tree （ The left subtree is greater than or equal to the root node , Right subtrees are all trees smaller than the root node ） If the preorder traversal sequence of is consistent, it will output YES, And output the post order traversal sequence of the tree , Otherwise output NO;

Ideas ： It's clear , First establish a binary search tree , And save its insertion sequence , Then the binary tree is searched for the preorder traversal sequence and the postorder traversal sequence , Do the same for mirror binary search tree （ Because there is no mirror binary search tree , Change the traversal condition according to the nature of mirror binary tree ）, Comparison between preorder traversal and insertion sequence , On the contrary, output the sequence after the output NO.

Code ：
 

#include<iostream>
#include<vector>
using namespace std;
int n,weight;
vector<int > oripre,pre,oripost,post,origin;
struct node{
	int data;
	node* lchild;// Pointer definitions cannot be separated by commas alone to define multiple pointers, such as node*  
	node* rchild;
};
void insert(node* &root,int x){// Insert and build a binary lookup tree , Remember to use &; 
	if(root==NULL){// Recursive boundary ; 
		root=new node;// yes root=new node instead of node* root=new node,root It has been defined and cannot be redefined , Otherwise, it will cover the original root The pointer ; 
		root->data=x;
		root->lchild=NULL;
		root->rchild=NULL;
		return ;
	}else if(x>=root->data){// Generally, it is inserted on the left , But the title is inserted on the right , The preorder traversal results of inserting left and inserting right are different , Pay attention to this ; 
		insert(root->rchild,x);// Recursive ; 
	}else{
		insert(root->lchild,x);
	} 
}

void oripreorder(node*  root,vector<int > &vi){// Traversal of binary search tree , Only a copy of the function is passed in , To operate on array values, you need &; 
	if(root==NULL)return ;
	vi.push_back(root->data);
	oripreorder(root->lchild,vi);
	oripreorder(root->rchild,vi); 
}

void preorder(node* root,vector<int > &vi){// Preorder traversal of mirror binary search tree , Use the original balanced binary tree , The traversal order becomes the root right and left ; 
	if(root==NULL)return ;
	vi.push_back(root->data);
	preorder(root->rchild,vi);
	preorder(root->lchild,vi);
}

void oripostorder(node* root,vector<int > &vi){// Post order traversal of the original binary search tree ; 
	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);// All start from the root node , Find the node that failed to search, which is the place to insert ; 
	}
	// Built a binary search tree ; 
	oripreorder(root,oripre);// Find the preorder traversal of binary search tree ;
	
	preorder(root,pre);// Preorder traversal of mirrored binary search tree , The way of traversing the same tree is different ;

	if(oripre==origin){// The insertion order of binary search tree is equal to the preorder traversal of binary search tree ; 
		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){// The preorder traversal sequence of the mirror binary search tree is equal to the insertion sequence ;
			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; 	
}

Be careful ：
 

1.

Generally, the value of the left subtree is less than or equal to the value of the root node , The right subtree is larger than the value of the root node , But if the topic has requirements, we should build up our achievements according to the requirements , Because the node equal to is on the left and on the right, the traversal sequence is different , If the insertion sequence is

8 6 7 5 10 8 11 Binary search tree of , If it is equal to on the left, the preorder traversal sequence is ：8 6 5 7 8 10 11

If it is equal to the right subtree, the preorder traversal sequence is ：8 6 7 5 10 8 11, So be optimistic about the requirements of the topic .

2.

What is passed into the function is a copy of the array , Destroy when used up , Operating on this copy within the function will not affect the original array , So if you want to change the array value in the function , Reference is required , Pass in the address of the array , Directly operate on the array ;

3.

The insertion of binary search tree affects the structure of the whole binary tree , That is, the establishment of child nodes will change the parent node on the upper level of recursion child Point to , therefore root Need to use references , After the child node is established, the point of the parent node is updated .

4.

Two vector You can directly assign values and compare whether they are equal , You don't need to use circular assignment like general arrays , Compare , take vector Just become a variable , Variables can be directly assigned and compared .