leetcode访谈问题33二叉搜索树的后序遍历序列,面试题


解题思路:因为是后序遍历序列,因此数组最后一个值是根节点,从头到尾依次比较每个元素和根节点的大小,如果是后序遍历序列应该可以将根节点前面的数组分为两个数组,一个数组所有元素都小于根节点,一个数组所有元素都大于根节点,如果不能完成这样的划分则返回True,如果可以就判断左子树序列和右子树序列是否是中序遍历序列。

class Solution:
    def verifyPostorder(self, postorder: List[int]) -> bool:
        size = len(postorder)
        if size == 0:
            return True
        i = 0
        while(i < (size-1) and postorder[i] < postorder[-1]):
            i += 1
        for j in range(i, size-1):
            if postorder[j] < postorder[-1]:
                return False
        return self.verifyPostorder(postorder[:i]) and self.verifyPostorder(postorder[i:-1])