三个月算法进阶--day63
目录
列表划分左右子树
二叉搜索树的充要条件(递归定义)
左子树的所有节点的值小于根节点，右子树所有节点的值大于根节点，左右子树也是二叉搜索树
记录
leetcode剑指offer第33题二叉搜索树的后序遍历序列
class Solution:
def verifyPostorder(self, postorder: List[int]) -> bool:
if not postorder or len(postorder) == 1:
return True
root = postorder[-1]
for i in range(len(postorder)):
if postorder[i] > root:
break
left = postorder[:i]
right = postorder[i:-1]
for i in right:
if i < root:
return False
return self.verifyPostorder(left) and self.verifyPostorder(right)
辅助单调栈(前序遍历、后序遍历倒序)
class Solution:
def verifyPostorder(self, postorder: [int]) -> bool:
stack, root = [], float("+inf")
for i in range(len(postorder) - 1, -1, -1):
if postorder[i] > root: return False
while (stack and postorder[i] < stack[-1]):
root = stack.pop()
stack.append(postorder[i])
return True