论坛 › C\C++交流 › PTA A_1043 Is It a Binary Search Tree

798236606 发表于 2020-2-14 15:36:43

PTA A_1043 Is It a Binary Search Tree

本帖最后由 798236606 于 2020-2-14 15:38 编辑

传送门：https://pintia.cn/problem-sets/994805342720868352/problems/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;
}

查看完整版本: PTA A_1043 Is It a Binary Search Tree