面试题24 二叉搜索树的后序遍历序列

题目描述

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出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 };