這道題關鍵在于判斷一棵樹是不是 BST
現在題目給出了樹的先序序列——我們可以知道這棵樹的根，然後題目也給出了 BST 的定義——左子樹 ＜ 根 ≤ 右子樹（BST 鏡像則是 左子樹 ≥ 根 ＞ 右子樹），那麼就可以确定左子樹、根、右子樹，進而确定這棵二叉樹。
是以我們可以通過根和根後續結點确定這棵樹是 BST 還是 BST 鏡像。如果是 BST，那麼後面的子樹也要全是 BST；否則後面的子樹全是 BST 鏡像
是以大概的思路就出來了：
/* 僞碼 */
int tree[maxn];//儲存輸入
bool flag = true;//由于判斷是否滿足 BST 特性需要所有子樹都滿足才真正滿足條件，而周遊涉及遞歸不太好傳回，是以設定個标志位用來判斷
void traversal(目前結點 n, 左子樹起始下标 base, 右子樹結束下标 end) {
/* 死胡同 */
if (base == end) {//葉子結點
n->data = tree[base];
n->left = n->right = NULL;
return;
}
/* 确定左子樹與右子樹 */
if (tree[base + 1] < n->data) {//左子樹比根小
//利用 BST 特性找到 tree[] 中第一個大于等于根的就是左右子樹分界
} else {
//同理
}
if (l - 1 != r) flag = false;//如果這個分界不是相差 1, 那就不滿足
/* 遞歸式 */
traversal(n->left, base, 分界線 - 1);
traversal(n->right, 分界線, end);
} 遺憾的是，最後程式 PA。我在 debug 時發現了一例邏輯錯誤的例子，留着後面再回顧了：
/*
暫時發現了一個邏輯錯誤的例子：
5
2 4 3 5 1
無論是 BST 還是 BST 鏡像最後輸出應該是 "NO" 而目前程式輸出 "YES"
錯誤原因是：
（如果按 BST 來組織）既然 [1] 比 [0] 大，那麼 [1] 後面的結點應該全是右子樹————全比 [0] 大；
（如果按 BST 鏡像來組織）既然 [1] 比 [0] 大，那麼 [1]~[3] 應該是左子樹————但這棵左子樹又不滿足 BST 特性
修改了很久都沒改出來，是以先放着 :-(
*/ 點選擷取完整代碼