本文共 967 字，大约阅读时间需要 3 分钟。

题目

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。

思路

同剑指offer书上思路，好理解很多！

代码

class Solution {public:
bool verifyPostorder(vector
   
    & postorder) {
    
if(postorder.size() <= 0){
    
return true;
    
}
    
int len = postorder.size();
    
return verify(postorder,0,len);
    
  }
    
bool verify(vector
    
     & postorder,int start,int len) {
     
int root = postorder[start + len - 1];
     
int i = 0;
     
//比较左子树和根，找到左子树结束位置
     
for(;i < len - 1;i++){
     
if(postorder[start +i] > root){
     
break;
     
}
     
}
     
int j = i;
     
//比较右子树和根，如果出现比根小的说明不存在这棵树
     
for(;j < len - 1;j++){
     
if(postorder[start +j] < root){
     
return false;
     
}
     
}
     
//递归比较左子树，如果为空的话就默认为true
     
bool left = true;
     
if(i > 0)
     
left = verify(postorder,start +0,i);
     
//递归比较右子树，如果为空的话就默认为true
     
bool right = true;
     
if(i < len-1-i)
     
right = verify(postorder,start + i,len-1-i);
     
return left && right;
     
}};
    
   

转载地址：https://blog.csdn.net/hanmin822/article/details/105674963 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！