题目描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true,否则返回false。假设输入的数组的任意两个数字都互不相同。（ps：我们约定空树不是二叉搜素树）
示例1
输入
[4,8,6,12,16,14,10]
返回值
true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| class Solution {
public:
bool VerifySquenceOfBST(vector<int> sequence) {
if(sequence.empty())
return false;
int end = *(sequence.end()-1);
bool result = true;
vector<int> left;
vector<int> right;
vector<int>::iterator iter = sequence.begin();
for(;iter!=sequence.end()-1;iter++)
if(end<*iter)
break;
vector<int>::iterator splitP = iter;
for(;iter!=sequence.end()-1;iter++)
if(end>*iter)
return false;
vector<int>::iterator bei = sequence.begin();
left.insert(left.end(),sequence.begin(),splitP);
right.insert(right.end(),splitP,sequence.end()-1);
bool leftFlag = (left.size()>1)?VerifySquenceOfBST(left):result;
bool rightFlag = (right.size()>1)?VerifySquenceOfBST(right):result;
return leftFlag&&rightFlag;
}
};
|