题目

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）的定义，以及镜像二叉树的定义，现在给出一个树的先序序列，判断该序列是否是一个二叉搜索树或者该树的镜像搜索树，如果是，输出该树的后序遍历序列，如果不是输出NO。
　　解题思路： 我们知道，仅凭一个先序遍历是无法确认一个树的结构的，但是如果该树是二叉搜索树，那么就可以确定该树的树形了。这道题的常规做法就是根据二叉树的定义以及先序序列进行建树，如果建树成功，说明该先序序列是某一个BST序列，否则不行。建树成功后，再对该树进行后序遍历，输出后序序列即可。
　　按照这个思路写，程序能写150+行的代码。其实有一个更巧妙的代码可以参考——
　　不妨考虑，先序遍历的第一个结点，必定是根结点。而二叉搜索树的特性，右边的都比左边的大，那么右子树的根结点必定比根结点和左子树都要大（大于或者等于），那么第一个大约等于根结点的结点，必定是右子树的根结点，这样就可以在先序序列中区分左右子树了。
　　
　　根据这个结论进行判断，右子树所有元素必定不小于根结点，左子树所有元素必定小于根结点。符合该定义之后，我们分别对左右子树递归判断。如果递归到最后一个元素，所有元素都符合，那么显然整个序列都是符合的。我们无需重新构建树结构，只从先序遍历序列中就能判断。
　　对于二叉搜索树，以上讨论都是成立的，我们利用了二叉搜索树的递归定义。对于镜像搜索树，只需把大小关系反过来就可以了。
　　同时，在递归的过程中，因为可以控制左右子树的访问时机，我们可以按照左右根的顺序存储当前根结点，即后序遍历序列，在判断的过程中就能得到后序遍历序列，可谓事半功倍。
　　更详细的细节，在代码注释中体现——

/*
** @Brief:No.1043 of PAT advanced level.
** @Author:Jason.Lee
** @Date:2018-12-18
** @Solution: https://blog.csdn.net/CV_Jason/article/details/85064315
*/
#include<iostream>
#include<queue>
using namespace std;

int node[1005],n;
int isBST;
queue<int> postOrder;
// 深度优先搜索 
void dfs(int l,int r,int isMirror)
{
    if (l>r||!isBST)
		return ;
    if (l==r){
		postOrder.push(node[l]);
		return;
	}
    int k=r+1;// k是用来记录右子树根结点的位置 
    for (int i=l+1;i<=r;i++)
    {
        if (node[i]<node[l]&&!isMirror) continue;//如果isMirror=0，说明是二叉搜索树，往右搜索找第一个比它大的，就是右子树根节点 
        if (node[i]>=node[l]&&isMirror) continue;//如果isMirror=1，说明是镜像搜索树，往有搜索找第一个比它小的，就是右子树根结点 
        k=i;// 找到右子树的根结点 
        break;
    }
   	// 判断右子树的右半部分 
    for (int i=k;i<=r;i++)
    {
        if (node[i]<node[l]&&!isMirror) isBST=0;// 对于二叉搜索树，如果右半部分存在比根结点小的点，显然不符合要求 
        if (node[i]>=node[l]&&isMirror) isBST=0;// 对于镜像搜索树，如果右半部分存在比更结点小的点，也不符合要求 
    }
    if (!isBST) return ;//发现不符合要求，立即停止搜索 
    dfs(l+1,k-1,isMirror);//递归搜索左子树 
    dfs(k,r,isMirror);//递归搜索右子树 
    postOrder.push(node[l]);// 根结点入队，符合后序遍历的顺序 
}
int main()
{
    cin>>n;
	// 输入节点 
    for(int i=1;i<=n;i++)
        cin>>node[i];
    isBST=1;
    //先比较序列的前两个数，判断可能是镜像搜索树还是二叉搜索树
    int isMirror=node[1]>node[2]?0:1;// isMirror 的作用判断是否Mirror 
    // 从根结点开始进行深度优先搜索 
	dfs(1,n,isMirror);
    if (!isBST) {
		cout<<"NO";
		return 0;
	}
    // 输出后序遍历 
	cout<<"YES"<<endl;
    cout<<postOrder.front();
    postOrder.pop();
    while(!postOrder.empty())
    {
        cout<<" "<<postOrder.front();
        postOrder.pop();
    }
    return 0;
}

总结

　　这道题的解法参考了网上某大神的解题报告，该做法同时考虑了二叉搜索树的特性、先序遍历的特性以及树的深度优先搜索，可谓出神入化，令人叹为观止。