1043 Is It a Binary Search Tree (25 分) 建立BST对比前序输出后序

墨蓝 2021-10-29 11:58 192阅读 0赞

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: ###

用给定的序列建立BST，比较这个序列是否与该BST前序or镜像前序相同

如果相同输出YES，打印该树的后序遍历。否则输出NO。

#include <stdio.h>
    #include <string.h>
    #include <string>
    #include <map>
    #include <queue>
    #include <math.h>
    #include <algorithm>
    #include <iostream>
    #define INF 0x3f3f3f3f
    using namespace std;
    struct Node
    {
    	int val;
    	struct Node *l,*r;
    	Node()
    	{
    		val=-1001;
    		l=r=NULL;
    	}
    };
    void insert(struct Node* root,int x)
    {
    	if(root->val==-1001)
    	{
    		root->val=x;
    		return;
    	}
    	if(x<root->val)
    	{
    		if(root->l==NULL)root->l=new Node;
    		insert(root->l,x);
    	}
    	else
    	{
    		if(root->r==NULL)root->r=new Node;
    		insert(root->r,x);
    	}
    }
    vector<int> k,pre,mpre,post,mpost;
    void preorder(Node* root)
    {
    	if(root==NULL) return;
    	pre.push_back(root->val);
    	preorder(root->l);
    	preorder(root->r);
    }
    void mpreorder(Node* root)
    {
    	if(root==NULL) return;
    	mpre.push_back(root->val);
    	mpreorder(root->r);
    	mpreorder(root->l);
    }
    void postorder(Node* root)
    {
    	if(root==NULL) return;
    	postorder(root->l);
    	postorder(root->r);
    	post.push_back(root->val);
    }
    void mpostorder(Node* root)
    {
    	if(root==NULL) return;
    	mpostorder(root->r);
    	mpostorder(root->l);
    	mpost.push_back(root->val);
    }
    int main()
    {
    	int n,x,i;
    	Node *root=new Node;
    	scanf("%d",&n);
    	for(i=0;i<n;i++)
    	{
    		scanf("%d",&x);
    		k.push_back(x);
    		insert(root,x);
    	}
    	preorder(root);
    	mpreorder(root);   
    	postorder(root);
    	mpostorder(root);
        
    	if(k==pre)
    	{
    		printf("YES\n");
    		for(i=0;i<post.size();i++)
    		{
    			if(i)printf(" ");
    			printf("%d",post[i]);
    		}
    		printf("\n");
    	}
    	else if(k==mpre)
    	{
    		printf("YES\n");
    		for(i=0;i<mpost.size();i++)
    		{
    			if(i)printf(" ");
    			printf("%d",mpost[i]);
    		}
    		printf("\n");
    	}
    	else
    	printf("NO\n");
    }