【剑指offer33】二叉搜索树的后序遍历序列

• 题目
  

• 解题思路
  根据后续遍历数组的特性,最后一个元素为根节点,前边分为左右子树两部分,且左子树部分数组元素值小于根节点值,右子树部分数组元素大于根节点值

题解链接
https://leetcode.cn/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/solution/by-hjfenghj-f-salr/

• code【自解】

class Solution {
    
public:
    bool verifyPostorder(vector<int>& postorder) {
    
        if(postorder.size()==0)
            return true;
        return process(postorder,0,postorder.size()-1);
    }

    bool process(vector<int>& postorder,int start,int end)
    {
    
        bool flag = true;   //标记以postorder[end]为根节点的树有没有右子树
        int temp = start-1; //左子树数组最后一个元素索引
        //basecase
        //当子树只包含一个元素时,一定true
        if(start == end)
            return true;
        //判断是否有右子树
        //根据后序遍历的数组特性,根节点postorder[end-1]的前驱节点为postorder[end-1]
        //如果 postorder[end-1] > postorder[end]说明右子树存在
        if(postorder[end-1] > postorder[end])
            flag = false;

        //无右子树,那么根节点postorder[end]前边的所有元素不能大于postorder[end]
        if(flag)
        {
    
            for(int i=end-1;i>=start;i--)
            {
    
                if(postorder[i] > postorder[end])
                    return false;
            }
        }
        //有右子树，那么就需要寻找左右子树的分界值
        for(int i=end-1;i>=start;i--)
        {
    
            if(postorder[i]<postorder[end])
            {
    
                //temp为最后一个左子树元素值
                temp = i;
                break;
            }
        }
        //分界索引temp前边的所用元素都属于postorder[end]的左子树,所以值不能大于根节点值
        for(int i=temp;i>=start;i--)
        {
    
            if(postorder[i] > postorder[end])
                return false;
        }

        bool res = true;
        if(start <= temp)
            res = res &&  process(postorder,start,temp);
        if(temp+1 <= end-1)
            res = res &&  process(postorder,temp+1,end-1);
        return res;
    }
};

• code 【官方】

class Solution {
    
public:
    bool verifyPostorder(vector<int>& postorder) {
    
        return process(postorder,0,postorder.size()-1);


    }
    bool process(vector<int>& postorder,int start,int end)
    {
    
        if(start>=end)
            return true;
        int cur = postorder[end];
        int p = start;
        while(postorder[p] < cur)  p++;
        int m = p;
        while(postorder[m] > cur)  m++;
        return m==end && process(postorder,start,p-1) && process(postorder,p,end-1); 
    }
};