PAT甲级1043、 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

思路

我没有想到什么特别好的思路，只能一边建树一边判断

如果能建出来一棵，那么就是可行的，建不出来的话就说明不行

建树的方法就是找到根（第一个位置），然后在树的其他部分找到第一个大于或小于根的元素，这里BST的话就找大于的，因为BST左子树全小于根，镜像的话就是小于的，注意，等于的元素是允许的，然后递归下去就可以了

要特别注意两种情况：

1、叶子节点没有孩子，要注意怎么判断出来

2、如果一棵树都只有左子树

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Node
{int val;Node* left;Node* right;
};
int tree[1001]={0};
bool BST = false,BOM = true;
Node* createTree(int l,int r,int min,int max)
{// cout<<"enter a node "<<l<<" "<<tree[l]<<endl;// cout<<l<<" "<<r<<" "<<min<<" "<<max<<endl;if(l>r || !BOM)return nullptr;if(tree[l] < min || tree[l] > max){BOM = false;return nullptr;}Node* root = new Node;root->val = tree[l];//这里对叶子节点的特判可有可无，不写也无所谓if(l==r){root->left = nullptr;root->right = nullptr;return root;}int start=l;for(;start<=r;start++){if(BST){if(tree[start] > tree[l])break;}else{if(tree[start] < tree[l])break;}}int lmi=min,lma=tree[l],rmi=tree[l],rma=max;if(!BST){lmi = tree[l];lma = max;rmi = min;rma = tree[l];}// cout<<start<<" "<<r<<endl;// cout<<lmi<<" "<<lma<<" "<<rmi<<" "<<rma<<endl;root->left = createTree(l+1, start-1,lmi,lma);root->right = createTree(start, r,rmi,rma);return root;
}
vector<int> post;
void postOrder(Node* root)
{if(root == nullptr)return ;postOrder(root->left);postOrder(root->right);post.push_back(root->val);
}
int main()
{int n;cin>>n;for(int i=0;i<n;i++){cin>>tree[i];}if(n > 1)for(int i=1;i<n;i++){// cout<<"i "<<tree[i]<<endl;if(tree[i] > tree[0]){BST = false;break;}if(tree[i] < tree[0]){BST = true;break;}}// cout<<BST<<endl;Node* root = createTree(0,n-1,-1, 10000);if(BOM){postOrder(root);cout<<"YES"<<endl<<post[0];for(int i=1;i<post.size();i++)cout<<" "<<post[i];cout<<endl;}elsecout<<"NO"<<endl;
}