笛卡尔树[天梯赛二叉树专项训练]

文章目录

题目描述
思路
AC代码

题目描述

在这里插入图片描述

输入样例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
NO

思路

见注释

AC代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
typedef struct node
{
    int data;
    struct node *left, *right;
}node;
int cnt; //记录是否能建立起一棵树
int num[N][2]; //存储每个节点的左子树和右子树的键值
int k1[N], k2[N]; //存储每个节点的K1和K2键值
bool flag_k2, flag_k1; //比较每个节点的左右子树是否都满足情况
vector<int> mid;
node* Init(int pos)
{
    if(pos == -1) return NULL; //当前节点不存在
    cnt ++;
    node* temp = new node;
    temp->data = pos;
    temp->left = NULL;
    temp->right = NULL;

    temp->left = Init(num[pos][0]); //左子树键值
    temp->right = Init(num[pos][1]); //右子树键值
    return temp;
}

void midorder(node* tree)
{
    if(tree)
    {
        midorder(tree->left);
        mid.push_back(tree->data);
        midorder(tree->right);
    }
}

void Judge(node* tree)
{
    //小根堆的特点，该节点左右子树的值均>该节点，即根节点的值最小
    if(tree->left)
    {
        if(k2[tree->data] > k2[tree->left->data])
        {
            flag_k2 = false;
            return;
        }
        Judge(tree->left);
    }

    if(tree->right)
    {
        if(k2[tree->data] > k2[tree->right->data])
        {
            flag_k2 = false;
            return;
        }
        Judge(tree->right);
    }
}
int main()
{
    flag_k1 = true;
    flag_k2 = true;
    int n;
    cin >> n;
    for(int i = 0; i < n; i ++)
    {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        k1[i] = a;
        k2[i] = b;
        num[i][0] = c;
        num[i][1] = d;
    }
    for(int i = 0; i < n; i ++)
    {
        cnt = 0;
        node* tree = Init(i);
        if(cnt == n) //这里没单独寻找根节点，因此采用对每个点假设为根节点，如果建立起来的树节点有n个，则该点就为根节点
        {
            midorder(tree); //中序遍历结果，用于后面判断左子树是否满足二叉搜索树的情况
            Judge(tree); //判断右子树是否为小根堆(k2是否满足条件)
            break;
        }
    }

    if(!flag_k2) cout << "NO" << endl;
    else //判断K1，二叉搜索树的中序遍历一定是递减的
    {
        for(int i = 0; i < mid.size() - 1; i ++)
        {
            if(k1[mid[i]] > k1[mid[i + 1]]) //判断中序遍历是不是递减序列，如果不是，则左子树不是二叉搜索树
            {
                cout << "NO" << endl;
                flag_k1 = false;
                break;
            }
        }
    }
    if(flag_k1 && flag_k2) cout << "YES" << endl;
    return 0;
}