本文共 1087 字，大约阅读时间需要 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 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！