描述

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true,否则返回false。假设输入的数组的任意两个数字都互不相同。（ps：我们约定空树不是二叉搜索树）   求解思路：

1. 通过递归依次判断子序列是否满足二叉搜索树构建条件。

代码：

 

 1 class Solution {
 2 public:
 3     bool VerifySquenceOfBST(vector<int> sequence) {
 4         // 不好找后序遍历有什么特点，那就根据这个序列判断是否满足二叉搜索树构建条件
 6         if(sequence.empty()){
 7             return false;
 8         }
 9         return correctST(sequence);
10     }
11     
12     bool correctST(vector<int> seq){
13         if(seq.empty()){
14             return true;
15         }
16         int len=seq.size();
17         int rootVal=seq[len-1];   // 找到当前序列的根节点
18         vector<int> leftTree,rightTree;
19         int i=0;
20         while(i<len-1){  // 左子树序列
21             if(seq[i]<rootVal){ // 不用考虑等于，因为都不重复
22                 leftTree.push_back(seq[i]);
23             }else{
24                 break;
25             }
26             ++i;
27         }
28         while(i<len-1){  // 右子树序列，如果序列中发现小于根节点的值，那直接返回fasle
29             if(seq[i]>rootVal){
30                 rightTree.push_back(seq[i]);
31             }else{
32                 return false;
33             }
34             ++i;
35         }
36         return correctST(leftTree) && correctST(rightTree);
37     }
38 };