PAT-甲级-1043 Is It a Binary Search Tree (二叉排序树性质）

题目描述：

给定一个序列，问你是不是二叉排序树的前序序列，如果是，输出YES和后序序列，否则输出NO，这个二叉排序树可以是左边>=根，右边<根或者相反

输入输出：

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

思路：

类似前面树的前序中序输出后序序列，假设当前是一棵左大右小二叉排序树，那么其前序第一个是根，后面>=根值的序列是左子树，<根值的是右子树
这样可以，递归这个过程。找到前序序列的右子树和右子树部分，它们也是二叉排序树，直至到只有一个节点，就加入后序序列，顺序是左右根

Code：

#include<iostream>
#include<vector>

using namespace std;

vector<int>pre;
vector<int>post;

void pre_to_post(int root, int end, bool is_mirror)
{
    if(root > end) return;

    int left_iter = root + 1, right_iter = end;
    if(!is_mirror)
    {
        while(left_iter <= end && pre[left_iter] < pre[root]) left_iter++;
        while(right_iter > root && pre[right_iter] >= pre[root]) right_iter--;
    }
    else
    {
        while(left_iter <= end && pre[left_iter] >= pre[root]) left_iter++;
        while(right_iter > root && pre[right_iter] < pre[root]) right_iter--;  
    }
    if(left_iter - 1 != right_iter) return;
    pre_to_post(root + 1, left_iter - 1, is_mirror);
    pre_to_post(right_iter + 1, end, is_mirror);
    post.push_back(pre[root]);
    
}
int main()
{
    int n;
    cin>>n;
    for(int i = 0; i < n; i++)
    {
        int t;
        cin>>t;
        pre.push_back(t);
    }
    bool  is_mirror = false;
    
    pre_to_post(0, n - 1, is_mirror);
    if(post.size() < n)
    {
        is_mirror = true;
        post.clear();
        pre_to_post(0, n - 1, is_mirror);
        if(post.size() < n)
        {
            cout<<"NO";  
            return 0;
        }
    }
        
    cout<<"YES"<<endl;
    cout<<post[0];
    for(int i = 1; i < n; i++)
       cout<<‘ ‘<<post[i]; 
}

PAT-甲级-1043 Is It a Binary Search Tree (二叉排序树性质）

原文：https://www.cnblogs.com/liushz-blog/p/14588164.html