PTA ladder game exercise set l2-004 search tree judgment

Search tree judgment

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

Ideas ： The characteristic of the preorder traversal result is that the first is the root node , Then left subtree and right subtree . The characteristic of preorder traversal of binary search tree is the root node , Larger than the left subtree , Smaller than the right subtree , Use two variables to traverse left to right and right to left on the array that needs to determine the result , Find the two intervals of the right child and the left child of the current root , See whether the difference of the interval is 1. The normal search tree is Left child interval , Right child interval , Then there is another root . So the left and right children's interval is the difference. This root interval is also the difference 1. Interval difference 1 If it meets the conditions, it is the search tree traversed by the previous order . If the image is larger than the left subtree and smaller than the right subtree, just change .

Pictured , The binary search tree has a root node and a left child interval and a right child interval . The difference between the right child and the left child is one . For example, the number in the figure 7 And number 10 It is the contact area of two child nodes ,7 The subscript for 3 The location of ,10 The subscript for 4 The location of , It's just one , With this feature, you can judge whether it is a binary search tree .
AC Code （C++）

#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 1010;					//  The maximum number 
int ismirr;								//  Mark whether it is a mirror tree 
int treeData[MAXN];						//  Save the pre order traversal data of the tree 

vector<int>vTreeData;					//  Save the post order traversal data of the tree 

void findNode(int Left, int right) 
{
    
	if (Left > right)					//  The left side of the interval must be less than the right side, otherwise it ends 
		return;
	//  In the current loop Left Is the root node of the secondary block 
	int tempRoot = Left;
	//  Characteristics of preorder traversal ： root   Left   Right , So find the child node from the right side of the root 
	//  So looking for an interval is next to the root （tempRoot + 1） In the end （right）
	int tempLeft = tempRoot + 1, tempRight = right;
	if (!ismirr)		//  Non mirrored tree left < Right 
	{
    
		while (tempLeft <= right && treeData[tempLeft] < treeData[tempRoot])
			tempLeft++;
		while (tempRight > Left && treeData[tempRight] >= treeData[tempRoot])
			tempRight--;
	}
	else				//  Image tree right > Left 
	{
    
		while (tempLeft <= right && treeData[tempLeft] >= treeData[tempRoot])
			tempLeft++;
		while (tempRight > Left && treeData[tempRight] < treeData[tempRoot])
			tempRight--;
	}
	//  The left and right of the interval are not 1 They don't meet the requirements 
	if (tempLeft - tempRight != 1) 
		return;
	//  Continue to search recursively according to the segmented interval , These two functions cannot be replaced 
	//  Because post order traversal requires left   Right   root 
	findNode(Left + 1, tempRight);
	findNode(tempLeft, right);
	//  Left   Right   root   So just put the found elements into the container , It is in line with the convenience of follow-up 
	vTreeData.push_back(treeData[Left]);
}

int main() 
{
    
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> treeData[i];
	ismirr = false;					//  Assume a non mirrored tree 
	findNode(0, n - 1);

	//  The container element is smaller than the number of input elements, indicating that it does not comply with the search tree traversal conditions 
	//  But it may also be the reason for the mirror tree, so judge the mirror tree method 
	if (vTreeData.size() != n) 
	{
    
		ismirr = true;				//  Mark as mirror tree 
		vTreeData.clear();			//  Empty the container 
		findNode(0, n - 1);
	}

	//  If the two rounds of judgment are not qualified, then it is not a search tree 
	if (vTreeData.size() != n)
		cout << "NO\n";
	else 
	{
    
		//  If it meets the conditions, output it in the format 
		cout << "YES\n";
		for (int i = 0; i < n; i++) 
		{
    
			//  Directly output the contents of the container, because the container is the result of post order traversal  
			cout << vTreeData[i];
			if (i == (n - 1))
				cout << endl;
			else
				cout << " ";
		}
	}
	return 0;
}