题解:1.题目给出了搜索二叉树的后序遍历,由搜索二叉树可知中序遍历的结果是递增数组,则可以把问题转化成后序遍历和中序遍历是否是通一个二叉树。
2.直接利用二叉树后序遍历的数组的最后一个数是该树的根节点的性质,将树划分成左右两个数组,两个数组必须满足【左边数据小于根节点,右边数组大于跟节点】。然后采用队列存储子树
class Solution: def VerifySquenceOfBST(self, sequence): # write code here def IsPost(seq): root=seq[-1] seq=seq[:-1] i=0 while i<len(seq) and seq[i]<root: i+=1 for j in range(i,len(seq)): if seq[j]<root: return None return i if not sequence: return False temp=[sequence] while temp: s=temp.pop(0) if len(s)<2: continue ind=IsPost(s) if ind==None: return False else: temp.append(s[:ind]) temp.append(s[ind:-1]) return True