专栏首页Don的成长史【PAT甲级】Is It a Binary Search Tree

【PAT甲级】Is It a Binary Search Tree

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

本文链接:https://blog.csdn.net/weixin_42449444/article/details/90143012

Problem Description:

A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:

  • The left subtree of a node contains only nodes with keys less than the node's key.
  • The right subtree of a node contains only nodes with keys greater than or equal to the node's key.
  • Both the left and right subtrees must also be binary search trees.

If we swap the left and right subtrees of every node, then the resulting tree is called the Mirror Image of a BST.

Now given a sequence of integer keys, you are supposed to tell if it is the preorder traversal sequence of a BST or the mirror image of a BST.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (≤1000). Then N integer keys are given in the next line. All the numbers in a line are separated by a space.

Output Specification:

For each test case, first print in a line YES if the sequence is the preorder traversal sequence of a BST or the mirror image of a BST, or NO if not. Then if the answer is YES, print in the next line the postorder traversal sequence of that tree. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.

Sample Input 1:

7
8 6 5 7 10 8 11

Sample Output 1:

YES
5 7 6 8 11 10 8

Sample Input 2:

7
8 10 11 8 6 7 5

Sample Output 2:

YES
11 8 10 7 5 6 8

Sample Input 3:

7
8 6 8 5 10 9 11

Sample Output 3:

NO

解题思路:

这道题考察到了很多关于树的知识,比如:①二叉搜索树的定义及构造;②二叉树的先序遍历、后序遍历;③二叉树的反转;④如何判断一颗二叉树是不是二叉搜索树。

用一个vector(原始序列v)来保存输入的先序遍历序列。根据输入的原始序列来构建一棵二叉搜索树bt,调用自定义函数preOrder()来得到二叉搜索树bt的先序遍历序列pre。一共有三种情况:①若先序序列pre和原始序列v相等就说明这是一棵二叉搜索树,输出"YES"并调用自定义函数postOrder()来得到二叉搜索树bt的后序遍历序列post,最后输出post即可;②若pre和v不相等,则调用自定义函数reverse()来将二叉搜索树的左右子树进行反转从而得到它的镜像,然后调用preOrder()来得到二叉搜索树镜像的先序遍历序列pre,若pre和v相等 说明这是二叉搜索树的镜像,输出"YES"并调用自定义函数postOrder()来得到二叉搜索树镜像的后序遍历序列post,最后post即可;③如果既不是一棵二叉搜索树,也不是一棵二叉搜索树的镜像 就输出"NO"。

解释一下这些自定义函数:我们都知道二叉搜索树的左子树的结点值都小于根结点的值,二叉搜索树的右子树的结点值都大于根结点的值,那么就可以根据这个性质来递归构造二叉搜索树:若二叉树根结点为空则新建一个根结点值为x的二叉树,若x小于根结点的值则插入到左子树,若x不小于根结点的值则插入到右子树。先序遍历和后序遍历这俩个自定义函数就不解释啦。反转二叉树这个自定义函数,我是通过无脑递归交换左右子树来实现的。

AC代码:

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

typedef struct TreeNode
{
    int data;   //结点值
    TreeNode *lchild,*rchild;   //左右子树
}*Tree;

void insert(Tree &root,int x)    //构造二叉搜索树
{
    if(root == NULL)   //若根结点为空则新建一个根结点值为x的二叉树
    {
        root = new TreeNode;
        root->data = x;
        root->lchild = root->rchild = NULL;
    }
    else if(x < root->data)   //若x小于根结点的值则把插入到左子树
    {
        //二叉搜索树的左子树上的结点值都小于根结点的值
        insert(root->lchild,x);
    }
    else   //否则将x插入到右子树
    {
        //二叉搜索树的右子树上的结点值都大于根结点的值
        insert(root->rchild,x);
    }
}

void preOrder(Tree root, vector<int> &pre)    //把二叉树先序遍历(中左右)的结果放入vector中
{
    if(root == NULL) return;
    pre.push_back(root->data);
    //cout << root->data << " ";
    preOrder(root->lchild,pre);
    preOrder(root->rchild,pre);
}

void postOrder(Tree root, vector<int> &post)    //把二叉树后序遍历(左右中)的结果放入vector中
{
    if(root == NULL) return;
    postOrder(root->lchild,post);
    postOrder(root->rchild,post);
    post.push_back(root->data);
    //cout << root->data << " ";
}

void print(vector<int> &v)   //输出vector
{
    bool isVirgin = true;   //判断是不是第一次
    for(auto it : v)
    {
        if(isVirgin)    //第一次直接输出数字
        {
            printf("%d",it);
            isVirgin = false;
        }
        else     //如果不是第一次了,则每次输出数字前先输出一个空格
        {
            printf(" %d",it);
        }
    }
    printf("\n");
}

void reverse(Tree root)     //二叉树的反转
{
    if(root == NULL) return;
    swap(root->lchild,root->rchild);
    reverse(root->lchild);
    reverse(root->rchild);
}

int main()
{
    int N;   //结点数N
    cin >> N;
    Tree bt = NULL;    //创建二叉树
    vector<int> v,pre,post;   //原始序列v、先序遍历序列pre、后序遍历序列post
    for(int i = 0; i < N; i++)
    {
        int temp;
        cin >> temp;
        insert(bt,temp);   //构建二叉搜索树
        v.push_back(temp);
    }
    preOrder(bt,pre);  //得到先序序列pre
    if(pre == v)   //若原始序列和先序序列相等,则说明bt是二叉搜索树
    {
        printf("YES\n");
        postOrder(bt,post);    //得到后序序列post
        print(post);
    }
    else
    {
        reverse(bt);   //把二叉搜索树进行反转,得出二叉搜索树的镜像
        pre.clear();   //清空先序序列
        preOrder(bt,pre);   //得到二叉搜索树的镜像的先序序列
        if(pre == v)
        {
            printf("YES\n");   //得到二叉搜索树的镜像的后序序列post
            postOrder(bt,post);
            print(post);
        }
        else
        {
            printf("NO\n");
        }
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【Codeforces】1217A - Creating a Character

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • 【GPLT】L1-007 念数字

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • 【PAT甲级】Sign In and Sign Out

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • 【AI专栏】语音合成系统评测介绍

    如何从多维度评价TTS系统质量成了TTS测试人员的一大挑战。本文针对TTS前端、后端的问题介绍了一种包括主观评测、客观评测TTS测试方法。

    腾讯移动品质中心TMQ
  • SAP Spartacus activeBaseSite的设置逻辑

    Jerry Wang
  • 跳图嵌入中与语义和语法相关的子向量(CS CompLang)

    我们研究出任何单词的跳图语法嵌入都可以分解为两个子向量,它们大致对应于单词的语义和句法作用。

    shellmik
  • linux下MBR分区表修复/恢复

    主引导记录(Master Boot Record,MBR),位于一个硬盘的0柱面、0盘面、1扇区,共512字节。具体划分依次为:引导代码区440字节、磁盘签名4...

    大大大黑白格子
  • Android Activity生命周期整理

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 串口+RS485驱动

    其实RS485不算什么协议,只是物理层做了差分传输,AB两线的电压差来表示0,1,0,1,可靠性和距离更加好,因此,一个串口外设只能作为半双工使用,而RS232...

    用户4645519
  • Cephfs的快照功能

    Cephfs的快照功能在官网都很少提及,因为即使开发了很多年,但是由于cephfs的复杂性,功能一直没能达到稳定,这里,只是介绍一下这个功能,怎么使用,并且建议...

    用户2772802

扫码关注云+社区

领取腾讯云代金券