用微信怎么做商城网站,1232网址之家,2022最新免费的推广引流软件,永久免费linux服务器笛卡尔树
题目描述 笛卡尔树是一种特殊的二叉树#xff0c;其结点包含两个关键字K1和K2。首先笛卡尔树是关于K1的二叉搜索树#xff0c;即结点左子树的所有K1值都比该结点的K1值小#xff0c;右子树则大。其次所有结点的K2关键字满足优先队列#xff08;不妨设为最小堆其结点包含两个关键字K1和K2。首先笛卡尔树是关于K1的二叉搜索树即结点左子树的所有K1值都比该结点的K1值小右子树则大。其次所有结点的K2关键字满足优先队列不妨设为最小堆的顺序要求即该结点的K2值比其子树中所有结点的K2值小。给定一棵二叉树请判断该树是否笛卡尔树。 输入描述 输入首先给出正整数N1N1000为树中结点的个数。随后N行每行给出一个结点的信息包括结点的K1值、K2值、左孩子结点编号、右孩子结点编号。设结点从0到(N-1)顺序编号。若某结点不存在孩子结点则该位置给出−1。 输出描述 输出YES如果该树是一棵笛卡尔树否则输出NO。 样例 输入 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 输出 YES 思路
先利用并查集找到树根然后从根开始遍历work1返回的是此节点及其所有子树中所有节点的最大值。根据笛卡尔树定义可得出判断条件: 若当前节点k1 work1(a[root].l) 则不是笛卡尔树若当前节点k1 work1(a[root].r) 则不是笛卡尔树 work2返回的是此节点及其所有子树中所有节点的最小值。根据笛卡尔树定义可得出判断条件: 若当前节点k2 min(work2(a[root].l),work2(a[root].r)) 则不是笛卡尔树 Code:
#includebits/stdc.h
using namespace std;
const int INF 1e9 10;
const int N 1e6 10;
struct Node {int k1,k2;int l,r;
} a[1010];
int p[1010];
int find(int x) {return p[x]x?x:p[x]find(p[x]);
}
bool ok11,ok21;
int work1(int root) {int t1,t2;t1t2-1;if(a[root].l!-1) t1 work1(a[root].l);if(a[root].r!-1) t2 work1(a[root].r);if(t1!-1 a[root].k1t1) ok10;if(t2!-1 a[root].k1t2) ok10;return max(a[root].k1,max(t1,t2));
}
int work2(int root) {int t1,t2;t1t2INF;if(a[root].l!-1) t1 work2(a[root].l);if(a[root].r!-1) t2 work2(a[root].r);if(a[root].k2min(t1,t2)) ok20;return min(a[root].k2,min(t1,t2));
}
int main() {int n;cin n;for(int i0; in; i) p[i]i;for(int i0; in; i) {cin a[i].k1 a[i].k2 a[i].l a[i].r;p[a[i].l] i;p[a[i].r] i;}int root;for(int i0; in; i) {if(find(i)i) {rooti;break;}}work1(root);work2(root);if(ok1ok2) puts(YES);else puts(NO);return 0;
}/**/
