Python数据结构算法，二叉搜索树的后序遍历序列

二叉搜索树的后序遍历序列

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

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

 5
    / \
   2   6
  / \
 1   3 

示例 1：

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

示例 2：

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

提示：

数组长度 <= 1000 

Code:

class Solution(object): def verifyPostorder(self, postorder): """
        :type postorder: List[int]
        :rtype: bool
        """ n = len(postorder) if not postorder: return True index = 0 for i in range(n): if postorder[i] >= postorder[-1]: index = i break for i in range(index+1,n-1): if postorder[i] < postorder[-1]: return False left = postorder[:index] right = postorder[index:-1] return self.verifyPostorder(left) and self.verifyPostorder(right) 

本文地址：https://blog.csdn.net/qq_34170700/article/details/108237117