题目描述

基本思路：
1.根据先序遍历，可知，比根小的值一定在左边，比根大的值一定在右边。 且这两部分值是有明显的分界线的
例如：
7
8 6 5 7 10 8 11
[6 5 7] 是左子树
[10 8 11]是右子树
2.用递归，就能找出所有左右子树了
3.输出”NO”的条件是：
在任意一层递归中，有任意一个值不属于左子树也不属于右子树 -> 代码实现就是 k < r, 没有遍历完整个子树

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1010;
int preorder[N],postorder[N],cnt;

bool cmp(int v1,int v2,int way){
    if(way) return v1 > v2;
    else return v1 <= v2;
}

bool is_search(int pl,int pr,int way){
    if(pr == pl) return true;

    int root = preorder[pl],k = pl + 1;
    bool fl = true;

    while(k < pr && cmp(root,preorder[k],way)) k++;
    if(!is_search(pl + 1,k,way)) fl = false;

    int l = k;
    while(k < pr && cmp(root,preorder[k],!way)) k++;
    if(k < pr || !is_search(l,k,way)) fl = false;

    postorder[cnt ++] = root;

    return fl;
}

int main(){
    int n;

    cin >> n;
    for(int i = 0; i < n; i++) cin >> preorder[i];

    if(is_search(0,n,preorder[0] > preorder[1])){
        puts("YES");

        cout << postorder[0];
        for(int i = 1; i < cnt; i++) cout << ' ' << postorder[i];
        return 0;
    }

    puts("NO");
    return 0;
}