题意：
Description
笛卡尔树是一种特殊的二叉树，其结点包含两个关键字K 1和K 2 。首先笛卡尔树是关于K 1 的二叉搜索树，即结点左子树的所有K 1 值都比该结点的K 1 值小，右子树则大。其次所有结点的K 2 关键字满足优先队列（不妨设为最小堆）的顺序要求，即该结点的K 2值比其子树中所有结点的K 2值小。给定一棵二叉树，请判断该树是否笛卡尔树。
Input
输入首先给出正整数N（≤ 1000），为树中结点的个数。随后N行，每行给出一个结点的信息，包括：结点的K 1值、K 2值、左孩子结点编号、右孩子结点编号。设结点从0 ∼ ( N − 1 ) 顺序编号。若某结点不存在孩子结点，则该位置给出−1。
Output
输出YES如果该树是一棵笛卡尔树；否则输出NO。
思路：
判断的重点在于：如何判断K1关键字的二叉搜索树，如果判断K2关键字的优先队列性质。
二叉搜索树的判断：中序遍历的K1序列是否为单调不递减序列
优先队列的判断：递归遍历的时候，判断子节点的K2值，是不是小于当前节点的K2值，以及，子节点是否满足此性质，递归判断就行了。
为了方便处理，把下标都加了1，这样就是从1开始了。
and 要先找到根节点，没有作为子节点的节点就是根节点，用map维护下就能找到。
代码：
#include <bits/stdc++.h> using namespace std; const int maxn=1e6+7; #define debug(x) cout<<#x<<":"<<x<<endl; int n,order[maxn],idx=0; struct node{ int val1,val2; int lson,rson; }a[maxn]; void dfs(int u){ if(a[u].lson!=-1) dfs(a[u].lson); order[++idx]=a[u].val1; if(a[u].rson!=-1) dfs(a[u].rson); } bool isBST(int root){ dfs(root);///中序遍历 for(int i=1;i<n;i++) if(order[i]>order[i+1]) return 0; return 1; } bool isHeap(int u){ if(u==-1) return 1; if(a[u].lson!=-1){ int t=a[u].lson; if(a[t].val2<a[u].val2) return 0; if(!isHeap(t)) return 0; } if(a[u].rson!=-1){ int t=a[u].rson; if(a[t].val2<a[u].val2) return 0; if(!isHeap(t)) return 0; } return 1; } int main() { map<int,int>mp; cin>>n; for(int i=1;i<=n;i++){ cin>>a[i].val1>>a[i].val2>>a[i].lson>>a[i].rson; if(a[i].lson!=-1) a[i].lson++,mp[a[i].lson]++; if(a[i].rson!=-1) a[i].rson++,mp[a[i].rson]++; } int root=1;///找到根节点 while(mp.count(root)) root++; ///debug(root); if(isBST(root)&&isHeap(root)) puts("YES"); else puts("NO"); return 0; }
