【pta】项目4-5 笛卡尔树 (25 分) <笛卡尔树判断>

2024-01-12 15:06:46

一、题目大意

题目链接：https://pintia.cn/problem-sets/15/problems/858

笛卡尔树是一种特殊的二叉树，其结点包含两个关键字K1和K2。首先笛卡尔树是关于K1的二叉搜索树，即结点左子树的所有K1值都比该结点的K1值小，右子树则大。其次所有结点的K2关键字满足优先队列（不妨设为最小堆）的顺序要求，即该结点的K2值比其子树中所有结点的K2值小。给定一棵二叉树，请判断该树是否笛卡尔树。

输入格式:

输入首先给出正整数N（≤1000），为树中结点的个数。随后N行，每行给出一个结点的信息，包括：结点的K1值、K2值、左孩子结点编号、右孩子结点编号。设结点从0~(N-1)顺序编号。若某结点不存在孩子结点，则该位置给出−1。

输出格式:

输出YES如果该树是一棵笛卡尔树；否则输出NO。

输入样例1:

6
8 27 5 1
9 40 -1 -1
10 20 0 3
12 21 -1 4
15 22 -1 -1
5 35 -1 -1

结尾无空行

输出样例1:

YES

结尾无空行

输入样例2:

6
8 27 5 1
9 40 -1 -1
10 20 0 3
12 11 -1 4
15 22 -1 -1
50 35 -1 -1

输出样例2:

二、ac代码

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

struct node{
int lchild,rchild,k1,k2;
}tree[10005];
int vis[10005],inorder[10005];
int n,root,cnt,flag1=1,flag2=1;
void inorder1(node a)
{
    if (cnt==n) return;
    if (a.lchild!=-1) inorder1(tree[a.lchild]);
    inorder[cnt++]=a.k1; //中序遍历，并插入数组
    if (a.rchild!=-1) inorder1(tree[a.rchild]);
}
bool search_tree()
{
    for (int i=0;i<n-1;i++)
    {
        if (inorder[i]>=inorder[i+1]) return false; //查看是否递增
    }
    return true;
}
void bfs()
{
    queue<node>qu;
    node cur;
    cur=tree[root];
    qu.push(cur);
    while(!qu.empty())
    {
        if (flag1==0||flag2==0)  return;
        cur=qu.front();
        qu.pop();
        if (cur.lchild!=-1)
        {
            if (cur.k2>=tree[cur.lchild].k2){ //判断是否最小堆
                flag2=0;
                break;
            }
            qu.push(tree[cur.lchild]);
        }
        if (cur.rchild!=-1) {
            if (cur.k2>=tree[cur.rchild].k2){
                flag2=0;
                break;
            }
            qu.push(tree[cur.rchild]);
        }

    }
}
int main(void)
{
    scanf("%d",&n);
    for (int i=0;i<n;i++)
    {
        scanf("%d %d %d %d",&tree[i].k1,&tree[i].k2,&tree[i].lchild,&tree[i].rchild);
        vis[tree[i].lchild]=1;
        vis[tree[i].rchild]=1;
    }
    for (int i=0;i<n;i++)
    {
        if (vis[i]==0){ //如果哪个编号不是别的点的子树，这个编号就是树的根
            root=i;
            break;
        }
    }
    inorder1(tree[root]);
    if (!search_tree()) flag1=0;
    bfs();
    if (flag1&&flag2) printf("YES");
    else printf("NO");
}

三、亿些知识点

搜索树的性质：每个节点的左儿子比该节点小，右儿子比该节点大（假设左右儿子都存在）

中序遍历：对于这棵树（包括其每一个子树），先访问左儿子，再访问父亲，最后访问其右儿子

对于搜索树的判断：对其中序遍历，访问的每个值都是递增的即是搜索树

这里我将整棵树排序了一下，比较直观

最小堆：父亲的值比左右儿子的值都要小的二叉树

这里我选择用队列的形式，依次访问根，左儿子，右儿子来判断是否是最小堆

感谢所有大佬的代码和思路~

peace

码农公寓