題目描述
輸入一個整數數組，判斷該數組是不是某二叉搜索樹的后序遍歷的結果。如果是則輸出Yes,否則輸出No。假設輸入的數組的任意兩個數字都互不相同。
1 class Solution { 2 public: 3 bool VerifySquenceOfBST(vector<int> sequence) { 4 if (sequence.size() == 0){ 5 return false; 6 } 7 if (sequence.size() == 1){ 8 return true; 9 } 10 int i = sequence.size()-1, k; 11 vector<int> v1, v2; 12 for (k = 0; k < i; k++){ 13 if (sequence[k] < sequence[i]){ 14 v1.push_back(sequence[k]); 15 } 16 else 17 break; 18 } 19 for (int j = k; j < i; j++){ 20 if (sequence[j] > sequence[i]){ 21 v2.push_back(sequence[j]); 22 } 23 else 24 return false; 25 } 26 bool left = true, right = true; 27 if (v1.size() >= 1) 28 left = VerifySquenceOfBST(v1); 29 if (v2.size() >= 1) 30 right = VerifySquenceOfBST(v2); 31 return left && right; 32 } 33 };
?
)
)
)
