PTA A_1043 Is It a Binary Search Tree

798236606

传送门：https://pintia.cn/problem-sets/9 ... /994805440976633856

解：
二叉搜索树的插入序列=前序遍历

#include<cstdio>
#include<vector>

using namespace std;

typedef struct node{
    int data;
    struct node *left, *right;
} BSTNode, *BSTree;

vector<int> insert_list, preorder_list;
int n;

bool mirror(int a, int b, bool flag)
{
    if (flag) return a < b;

    return a >= b;
}

void insert(BSTree &T, int temp, bool flag)
{
    if (!T)
    {
        T = new BSTNode;
        T->data = temp;
        T->left = T->right = NULL;
    }
    else
        mirror(temp, T->data, flag) ? insert2(T->left, temp, flag) : insert2(T->right, temp, flag);
}

void preorder(BSTree T)
{
    if (T)
    {
        preorder_list.push_back(T->data);
        preorder(T->left);
        preorder(T->right);
    }
}

void postorder(BSTree T)
{
    if (T)
    {
        postorder(T->left);
        postorder(T->right);
        printf("%d", T->data);
        if (--n) putchar(' ');
    }
}

int main(void)
{
    BSTree T1 = NULL, T2 = NULL;

    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        int temp;

        scanf("%d", &temp);
        insert(T1, temp, false);
        insert(T2, temp, true);
        insert_list.push_back(temp);
    }

    preorder(T1);

    if (preorder_list == insert_list)
    {
        puts("YES");
        postorder(T1);
    }
    else
    {
        preorder_list.clear();
        preorder(T2);

        if (preorder_list == insert_list)
        {
            puts("YES");
            postorder(T2);
        }
        else
            puts("NO");
    }

    return 0;
}