剑指 Offer 33. 二叉搜索树的后序遍历序列

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

参考以下这颗二叉搜索树：

     5

    / \

   2   6

  / \

 1   3

示例 1：

输入: [1,6,3,2,5]

输出: false

示例 2：

输入: [1,3,2,6,5]

输出: true

class Solution:
   def verifyPostorder(self, postorder: List[int]) -> bool:
       def judgeCur(i,j):
           if i>=j:return True
           p=i
           while postorder[p]<postorder[j]: p+=1
           m=p
           while postorder[p]>postorder[j]: p+=1
           if p!=j:return False
           else:
               return judgeCur(i,m-1)and judgeCur(m,j-1)
       return judgeCur(0,len(postorder)-1)
# 因为是排序二叉树，所以左<中<右
# 因此先找到最后的为根节点，从数组左侧开始遍历找到大于根节点的点，从这个点开始为右子树，前面的是左子树。
# 关键在于判断右子树中的值是否全部大于根节点