题目链接：点击打开链接
题目大意：二叉排序树 + 最小堆判定。
解题思路：这个题只要分开判断这个树的 k1 是否符合二叉排序树，k2 是否符合最小堆即可。最小堆的判断就是从根节点开始，看他的左右孩子的 k2 是否都比根节点的 k2 大，如果是则继续递归，否则 flag = 0 退出循环。
k1 的判断更简单，只要中序遍历一遍 k1 的值，看知否符合从小到大的排序即可。
其中在找根节点的时候利用 par 数组，将有父亲节点的孩子标记，则最后那个没有标记（没有父亲的）就是根节点了。
AC 代码
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a); #define INF 0x3f3f3f3f using namespace std; typedef long long ll; struct node { int l,r,k1,k2; }nds[1010]; int par[1010], a[1010], b[1010]; int flag, len; void init() { flag=1; len=0; mem(par,0); } void jde_BST(int rt) { if(rt!=-1) { jde_BST(nds[rt].l); a[len]=b[len]=nds[rt].k1; len++; jde_BST(nds[rt].r); } } void jde_MinHeap(int rt) { if(!flag) return; int l,r; if(nds[rt].l!=-1) { l=nds[rt].l; if(nds[rt].k2>nds[l].k2) { flag=0; return; } jde_MinHeap(l); } if(nds[rt].r!=-1) { r=nds[rt].r; if(nds[rt].k2>nds[r].k2) { flag=0; return; } jde_MinHeap(r); } } int main() { int n; while(~scanf("%d",&n)) { init(); int k1,k2,l,r; for(int i=0;i<n;i++) { scanf("%d%d%d%d",&k1,&k2,&l,&r); nds[i].k1=k1, nds[i].k2=k2, nds[i].l=l, nds[i].r=r; if(l!=-1) par[l]=1; if(r!=-1) par[r]=1; } int rt; for(int i=0;i<n;i++) // 找根节点 if(par[i]==0){ rt=i; break; } jde_MinHeap(rt); if(!flag){ puts("NO"); continue; } jde_BST(rt); sort(a,a+len); for(int i=0;i<len;i++) if(a[i]!=b[i]) { flag=0; break; } puts(flag?"YES":"NO"); } return 0; }
