立志用最少的代碼做最高效的表達

---

笛卡爾樹是一種特殊的二叉樹，其結點包含兩個關鍵字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:
NO

---

分別判斷是否為小根堆和二叉平衡樹即可。
判斷小根堆：是否是一個遞增的序列
判斷二叉平衡樹：中序序列是否為一個遞增的序列。

---

#include<iostream> #include<cstdio> #include<vector> using namespace std;int n; struct node{int k1, k2;int left, right; }nod[1010]; int vis[1010]; //找根節點 //判斷是否為二叉搜索樹：判斷其中序序列是否為遞增。 vector<int>in; void isBst(int root) {if(nod[root].left != -1) isBst(nod[root].left);in.push_back(nod[root].k1);if(nod[root].right != -1) isBst(nod[root].right); } bool isBST(int root) {isBst(root);for(int i = 0; i < n-1; i++) if(in[i] > in[i+1]) return false;return true; }int isMinHeap(int root) {if(root == -1) return 1;if(nod[root].left != -1) if(nod[nod[root].left].k2 < nod[root].k2 || !isMinHeap(nod[root].left)) return 0;if(nod[root].right != -1) if(nod[nod[root].right].k2 < nod[root].k2 || !isMinHeap(nod[root].right)) return 0;return 1; }int main() {cin >> n;for(int i = 0; i < n; i++) {cin >> nod[i].k1 >> nod[i].k2 >> nod[i].left >> nod[i].right;if(nod[i].left != -1) vis[nod[i].left] = 1;if(nod[i].right != -1) vis[nod[i].right] = 1;; }int root = 0;for(int i = 0; i < n; i++) if(vis[i] == 0) root = i;cout << ((isBST(root) && isMinHeap(root)) ? "YES\n" : "NO\n"); return 0; }

---

耗時

---

總結

以上是生活随笔為你收集整理的笛卡尔树 (25 分)笛卡尔树是一种特殊的二叉树，其结点包含两个关键字K1和K2。首先笛卡尔树是关于K1的二叉搜索树，即结点左子树的所有K1值都比该结点的K1值小，右子树则大。其次所有结点的K2关键字的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。