原题链接 PAT甲级 1043 Is It a Binary Search Tree （25 分）

题目大意 给定一棵先序遍历的树，判断是二叉搜索树还是镜像的二叉搜索树（即左子树的值大于或等于根节点的值，右子树的值小于根节点的值）。如果是，输出"YES"，并对其进行后序遍历并输出。反之输出"NO"。

分析 我的思路比较简单，因为先序遍历是根左右，如果第一个元素的值大于第二个元素的，按照BST的形式建立这棵树。反正，按照镜像BST建立这棵树（使用DFS建立）。
然后对建立好的树进行先序遍历，将遍历的结果与给定的先序遍历做比较，如果相等则输出"YES"，并进行后序遍历，反之输出"NO"。

#include<iostream>
#include<vector>
using namespace std;
struct node{
    int val;
    node *left;
    node *right;
    node(int x) : val(x), left(NULL), right(NULL) {}
};
int n;
vector<int> tree, pre, post;
void dfs(node *root, int v){
  // BST形式
    if(root->val <= v){
        if(root->right==NULL){
            root->right = new node(v);
            return;
        } else{
            dfs(root->right, v);
        }
    } else{
        if(root->left==NULL){
            root->left = new node(v);
            return;
        } else{
            dfs(root->left, v);
        }
    }
}
void dfsmi(node *root, int v){
  // 镜像BST形式
    if(root->val <= v){
        if(root->left==NULL){
            root->left = new node(v);
            return;
        } else{
            dfsmi(root->left, v);
        }
    } else{
        if(root->right == NULL){
            root->right = new node(v);
            return; 
        } else{
            dfsmi(root->right, v);
        }
    }
}
void preorder(node *root){
    if(root!=NULL){
        pre.push_back(root->val);
        preorder(root->left);
        preorder(root->right);
    } else{
        return;
    }
}
void postorder(node *root){
    if(root==NULL)  return;
    postorder(root->left);
    postorder(root->right);
    post.push_back(root->val);
}
int main(){
    scanf("%d", &n);
    tree.resize(n);
    for(int i=0;i<n;i++){
        scanf("%d", &tree[i]);
    }
    node *root = new node(tree[0]);
    if(tree[0]>tree[1]){
        for(int i=1;i<n;i++)    dfs(root, tree[i]);
    } else {
        for(int i=1;i<n;i++)    dfsmi(root, tree[i]);
    }
    preorder(root);
    for(int i=0;i<n;i++){
        if(tree[i]!=pre[i]){
            printf("NO");
            return 0;
        }
    }
    postorder(root);
    printf("YES\n%d", post[0]);
    for(int i=1;i<n;i++)    printf(" %d", post[i]);
    return 0;
}