GPLT L2-004. 这是二叉搜索树吗？后序遍历

题目链接戳这里
因为是二叉搜索树,不论子树还是左右镜像的子树,根必然都是最大值,于是可以根据相对根的值的大小区分出左子树和右子树.

求出左子树和右子树的相对区间后即可递归操作,建立完左右子树后记录路径,即后序路径.先试试正向建树,不行再镜像建树.

这里留意return的条件,递归操作的区间是闭区间[rt,t] dfs前面的if(rt>t)return是确保区间内有元素.这是遍历树本应该做的判断, 后面的if-return主要是因为:若是合格的二叉搜索树,左区间的右界必然和右区间的左界相邻,若不相邻证明i和j在某个点被不合理的值卡住了,return是因为发现了异常,而这也是导致后续遍历缺少顶点,从而能判断非二叉排序树的根源.
比如序列[5,2,6,3], 根是5,下标0,左子树是{2},右子树本应是{6,3},但因3,右子树的左界下标被卡在3,因为左右子树不相邻,失败,返回,后序遍历缺少这颗坏树的点,最终反应出树不合理.

// 查找示意图
// 8 6 5 7 10 8 11
// |     |  |
// rt    j  i

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define pb push_back
const int inf = 0x3f3f3f3f, maxN = 1005;
int N, M, mirror;
vector<int> pre, post;

void get_post(int rt, int t) {
    if (rt > t)
        return;
    int i = rt + 1, j = t;
    if (!mirror) {
        while (i <= t && pre[i] < pre[rt]) ++i;
        while (j > rt && pre[j] >= pre[rt]) --j;
    } else {
        while (i <= t && pre[i] >= pre[rt]) ++i;
        while (j > rt && pre[j] < pre[rt]) --j;
    }
    if (i - j != 1)
        return;
    get_post(rt + 1, j);
    get_post(i, t);
    post.pb(pre[rt]);
}

int main() {
    // freopen("data.in", "r", stdin);
    scanf("%d", &N);
    pre.resize(N);
    rep(i, 0, N)
        scanf("%d", &pre[i]);
    get_post(0, N - 1);
    if (post.size() != N) {
        mirror = 1;
        post.clear();
        get_post(0, N - 1);
    }
    if (post.size() != N) {
        printf("NO");
    } else {
        printf("YES\n%d", post[0]);
        rep(i, 1, N)
            printf(" %d", post[i]);
    }
    return 0;
}