PTA search tree judgment

4-2- Binary search tree Search tree judgment (25 branch )

For binary search trees , We stipulate that the left subtree of any node contains only the key values which are strictly smaller than the node , And its right subtree contains the key value greater than or equal to the node . If we swap the left and right subtrees of each node , The resulting tree is called a mirror binary search tree .

Now let's give a sequence of integer key values , Please write a program to judge whether the sequence is a preorder traversal sequence of a binary search tree or a mirror binary search tree , If it is , Then output the post order traversal sequence of the corresponding binary tree .

Input format :
The first line of input contains a positive integer N（≤1000）, The second line contains N It's an integer , For the given sequence of integer key values , Numbers are separated by spaces .

Output format :
The first line of the output first gives the judgment result , If the input sequence is the preorder traversal sequence of a binary search tree or a mirror binary search tree , The output YES, No side output NO. If it turns out that YES, The next line outputs the post order traversal sequence of the corresponding binary tree . Numbers are separated by spaces , But there can't be extra spaces 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 6 8 5 10 9 11

sample output 2:

NO

The main idea is
1. Generate binary search tree （ The preorder traversal of a binary search tree must be equal , Therefore, it can be used to judge whether it belongs to the preorder traversal of a search tree ）（ We have been struggling with different sequences before, but the search trees built with the same number are not necessarily the same ）
2. Judge whether the preorder traversal of the search tree is the same as that given

#include<stdio.h>
#include<stdlib.h>
#define max 10000
int a[max], b[max],c[max];
int t;// Global variables are also very useful 
typedef struct node* Tree;
struct node {
    
	int data;
	Tree Left;
	Tree Right;
};
Tree Insert(Tree T, int x)
{
    
	if (T == NULL) {
            // Recursive export , In recursive programs, I think this is actually the hardest thing to think of 
		T= (Tree)malloc(sizeof(struct node));
		T->data = x;
		T->Left = T->Right = NULL;
	}
	else {
    
		if (x <T->data) {
    
			T->Left = Insert(T->Left, x);
		}
		else {
    
			T->Right = Insert(T->Right, x);
		}
	}
	return T;
}
Tree swap(Tree T)
{
    
	if (T) {
      // If you use T->Left&&T->Right, Then when one is empty and the other is not empty, there will be segment errors , Exchange from the lower layer 
		T->Left = swap(T->Left);
		T->Right = swap(T->Right);
		Tree tmp;
		tmp = T->Left;
		T->Left = T->Right;
		T->Right = tmp;
	}
	return T;
}
void pre(Tree T)//  The first sequence traversal 
{
    
	if (T) {
    
		b[t++] = T->data;
		pre(T->Left);
		pre(T->Right);
	}
}
void post(Tree T)
{
    
	if (T) {
    
		post(T->Left);
		post(T->Right);
		c[t++] = T->data;
	}
}
int main()
{
    
	int n,flag=0,i;
	Tree T = NULL,T1;
	scanf("%d", &n);
	for (int k = 0; k < n; k++) {
    
		scanf("%d", &a[k]);
		T=Insert(T, a[k]);
	}
	if (n == 1) {
    
		printf("YES\n%d", a[0]);
		return 0;
	}
	t = 0;// Every time you call pre perhaps post To initialize 
	pre(T);//b
	for (i = 0; i < n; i++) {
    
		if (a[i] != b[i]) {
    
			flag++;
			break;
		}
	}
	if (flag == 0) {
    
		t = 0;
		post(T);
		printf("YES\n");
		for (i = 0; i < n; i++) {
    
			if (i == 0)printf("%d", c[i]);
			else printf(" %d", c[i]);
		}
	}
	else {
    
		t = 0;
		T1=swap(T);
		pre(T1);
		for (i = 0; i < n; i++) {
    
			if (a[i] != b[i]) {
    
				flag++;
				break;
			}
		}
		if (flag == 1) {
    
			t = 0;
			post(T);
			printf("YES\n");
			for (i = 0; i < n; i++) {
    
				if (i == 0)printf("%d", c[i]);
				else printf(" %d", c[i]);
			}
		}
		else
			printf("NO");
	}
	return 0;
}

attach ： Search trees built with different sequences but the same number are not necessarily the same

Description
Judge whether two sequences are the same binary search tree sequence

Input
Start a number n,(1<=n<=20) Express n One needs to be judged ,n= 0 The end of the input .
The next line is a sequence , The sequence length is less than 10, contain (0~9) The number of , No repetition of numbers , According to this sequence, a binary search tree can be constructed .
It follows that the n Yes n A sequence of , Each sequence has the same format as the first sequence , Please judge whether these two sequences can form the same binary search tree .

Output
If the sequence is the same, output YES, Otherwise output NO

Sample Input
6

45021

12045

54120

45021

45012

21054

50412

0

Sample Output
NO

NO

YES

NO

NO

NO

HINT
Source