（1）題目描述 題目描述： 輸入一個整數數組，判斷該數組是不是某二叉搜索樹的後序遍歷的結果。如果是則輸出Yes,否則輸出No。假設輸入的數組的任意兩個數字都互不相同。 輸入： 每個測試案例包括2行： 第一行為1個整數n(1<=n<=10000)，表示數組的長度。 第二行包含n個整數，表示這個數組，數組中的數的范圍是[0,100000000]。 輸出： 對應每個測試案例，如果輸入數組是某二叉搜索樹的後序遍歷的結果輸出Yes，否則輸出No （2）程序實現 二叉搜索樹的性質是：元素的左子樹上的元素全部小於該元素，右子樹上的元素全部大於該元素。後序遍歷根節點總是在最後，所以根據後序遍歷順序可以得到根元素，並且得到根元素的左子樹和右子樹。假設樹的後序遍歷順序為：3,7,4,6,5；可以判斷出：5是根節點，3為根節點的左子樹，7,4,6是根節點的右子樹，但是右子樹需要保證所有節點大於根節點，所以這個順序不是二叉搜索樹的後序遍歷順序。 解題思路：在標識出左右子樹時，遍歷右子樹，發現右子樹中的元素小於其父節點，則順序為錯誤的。（PS：這種解法還需要優化，目前想到的辦法是存儲兩個變量，標識子樹中元素的最大值和最小值，還需要優化） [cpp] #include <iostream> using namespace std; bool IsValid(int *data, int n, int left, int right) { if(left>=right) return true; int mid = 0; int root = data[right]; //標識左子樹，右子樹的分割位置 for(mid = left; mid<right,data[mid]<root; ++mid) ; //判斷子樹是否合法 for(int i=mid; i<right; ++i) { if(data[i]<root) return false; } if(!IsValid(data, n, left, mid-1)) return false; if(!IsValid(data, n, mid+1, right)) return false; return true; } int main() { int n; while(cin>>n) { int *data = new int[n]; for(int i=0; i<n; ++i) cin>>data[i]; if(!IsValid(data, n, 0, n-1)) cout<<"No"<<endl; else cout<<"Yes"<<endl; delete[] data; } }
