L2-004 二叉搜索树

#include <stdio.h>
#include <stdbool.h>

#define MAX_N 1000

int pre[MAX_N];          // 存储前序遍历序列
int post[MAX_N];         // 存储后序遍历序列
int post_idx = 0;        // 后序遍历的索引
bool is_mirror = false;  // 是否是镜像的标志

// 检查是否是二叉搜索树或其镜像的前序遍历
bool is_bst(int left, int right) {
    if (left > right) return true;  // 递归终止条件

    int root = pre[left];  // 当前子树的根节点
    int i = left + 1;      // 左子树的起始位置
    int j = right;         // 右子树的结束位置

    if (!is_mirror) {
        // 检查左子树（所有值小于根节点）
        while (i <= right && pre[i] < root) i++;
        // 检查右子树（所有值大于等于根节点）
        while (j > left && pre[j] >= root) j--;
    } else {
        // 检查镜像的左子树（所有值大于等于根节点）
        while (i <= right && pre[i] >= root) i++;
        // 检查镜像的右子树（所有值小于根节点）
        while (j > left && pre[j] < root) j--;
    }

    // 如果左子树和右子树的边界不匹配，则不是BST或其镜像
    if (i - j != 1) return false;

    // 递归检查左子树和右子树
    bool left_valid = is_bst(left + 1, j);
    bool right_valid = is_bst(i, right);

    // 将根节点加入后序遍历序列
    post[post_idx++] = root;

    return left_valid && right_valid;
}

int main() {
    int N;
    scanf("%d", &N);  // 输入节点数

    // 输入前序遍历序列
    for (int i = 0; i < N; i++) {
        scanf("%d", &pre[i]);
    }

    // 先假设是BST，检查是否满足条件
    bool valid = is_bst(0, N - 1);

    if (!valid) {
        // 如果不是BST，尝试检查是否是镜像
        is_mirror = true;
        post_idx = 0;  // 重置后序遍历索引
        valid = is_bst(0, N - 1);
    }

    if (valid) {
        printf("YES\n");  // 输出YES
        // 输出后序遍历序列
        for (int i = 0; i < N; i++) {
            if (i != 0) printf(" ");
            printf("%d", post[i]);
        }
        printf("\n");
    } else {
        printf("NO\n");  // 输出NO
    }

    return 0;
}