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

LCR 152. 验证二叉搜索树的后序遍历序列

class VerifyTreeOrder:"""LCR 152. 验证二叉搜索树的后序遍历序列https://leetcode.cn/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/description/"""def solution(self, postorder: List[int]) -> bool:return self.check(postorder, 0, len(postorder) - 1)# 检查postorder[i, j] 是否为BSTdef check(self, postorder, i, j):if i >= j:return Trueroot = postorder[j]#  postorder[i..left) 是左⼦树，应该都⼩于 rootleft = iwhile left < j and postorder[left] < root:left += 1#  postorder[left..j) 是右⼦树，应该都大于 rootright = leftwhile right < j and postorder[right] > root:right += 1if right != j:return False# 递归检查左⼦树 [i..left) 和右⼦树 [left..j) 也符合 BST 的性质return self.check(postorder, i, left - 1) and self.check(postorder, left, j - 1)