题目描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
解题思路
对于一个后序序列S，如果去掉S的最后一个元素x得到序列S’，那么S’满足：S’可以分成两段，前一段（左子树）小于x，后一段（右子树）大于x，且这两段（子树）都是后序序列。
代码实现
class Solution {
private:
bool judge(vector
<int> &sequence
, int left
, int right
){
if(left
>= right
)
return true;
int i
= right
;
while(i
> left
&& sequence
[i
- 1] > sequence
[right
])
i
--;
for(int j
= i
- 1; j
>= left
; j
--)
if(sequence
[j
] > sequence
[right
])
return false;
return (judge(sequence
, left
, i
- 1) && judge(sequence
, i
, right
- 1));
}
public:
bool VerifySquenceOfBST(vector
<int> sequence
) {
if(sequence
.size() == 0)
return false;
return judge(sequence
, 0, sequence
.size() - 1);
}
};
运行结果
运行时间：4ms 占用内存：376k
