题解 | #二叉搜索树的后序遍历序列#
二叉搜索树的后序遍历序列
http://www.nowcoder.com/practice/a861533d45854474ac791d90e447bafd
思路:(seq=[4,8,6,12,16,14,10])
seq[-1]为二叉搜索树的root。根据root可以将seq分为left=[4,8,6]和right=[12,16,14]两部分,对right中的元素进行遍历,如果存在小于root的元素,说明不能组成二叉搜索树。
否则,再对left和right分别进行判断,方法同上。
递归退出的条件:len(se)=1
代码:
class Solution:
def VerifySquenceOfBST(self, sequence): # write code here if len(sequence)==0: return False if len(sequence)==1: return True root=sequence[-1] left=[] right=[] for i in range(len(sequence)-1): if sequence[i]<root: left.append(sequence[i]) else: break right=sequence[len(left):len(sequence)-1] for j in range(len(right)): if right[j]<root: return False l= True r=True if len(left)>0: l=self.VerifySquenceOfBST(left) if len(right)>0: r=self.VerifySquenceOfBST(right) return l and r