二叉搜索树的后序遍历序列
题目描述：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes/True,否则输出No/False。假设输入的数组的任意两个数字都互不相同。
【注：二叉搜索树(Binary Search Tree)又叫二叉查找树/二叉排序树，对于非空的二叉树，具有以下性质：
a)左子树上所有结点的值都小于它的根结点的值；
b)右子树所有结点的值都大于它的根结点的值；
c)左、右子树也分别为二叉搜索树。】
思路：
利用二叉搜索树的性质，来判断给定的数组是否能够与一个具体的二叉搜索树的后序遍历序列对应。
1. 如果是后序遍历序列，则序列最后一个元素为根节点，找到序列中第一个比根节点大的值并保存其索引，该值的左侧为左子树节点，该值及其的右侧去除最后节点值可先默认全部为右子树节点；
2. 如果上述划分的右子树节点的值如果有小于根节点的值，则不是后序遍历序列；
3. 在左子树和右子树中分别递归。
# -*- coding:utf-8 -*-class Solution:def VerifySquenceOfBST(self, sequence):# write code here# print(sequence)n=len(sequence)index=0leftsequence=[]rightsequence=[]if n==0:return Falsefor i in range(n):if sequence[i]>sequence[-1]:leftsequence=sequence[:i] #该值的左侧为左子树rightsequence=sequence[i:-1] #该值及其的右侧去除最后节点可先默认全部为右子树index=i #序列中第一个比根节点大的值value并保存其索引breakfor j in rightsequence: #如果右子树中有小于根节点的值，则不是后序遍历序列if j<sequence[-1]:return FalseleftTree=TruerightTree=Trueif len(sequence[:index])>0:leftTree=self.VerifySquenceOfBST(sequence[0:index]) #左子树是否为二叉搜索树if len(sequence[index:-1])>0:rightTree=self.VerifySquenceOfBST(sequence[index:-1]) #右子树是否为二叉搜索树#print(leftTree , rightTree)return leftTree and rightTree
测试：
s=Solution()a=[1,3,2,5,7,6,4]print(s.VerifySquenceOfBST(a))b=[1,3,2,7,5,6,4]print(s.VerifySquenceOfBST(b))#result：TrueFalse
二叉搜索树的后序遍历序列
题目描述：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes/True,否则输出No/False。假设输入的数组的任意两个数字都互不相同。
【注：二叉搜索树(Binary Search Tree)又叫二叉查找树/二叉排序树，对于非空的二叉树，具有以下性质：
a)左子树上所有结点的值都小于它的根结点的值；
b)右子树所有结点的值都大于它的根结点的值；
c)左、右子树也分别为二叉搜索树。】
思路：
利用二叉搜索树的性质，来判断给定的数组是否能够与一个具体的二叉搜索树的后序遍历序列对应。
1. 如果是后序遍历序列，则序列最后一个元素为根节点，找到序列中第一个比根节点大的值并保存其索引，该值的左侧为左子树节点，该值及其的右侧去除最后节点值可先默认全部为右子树节点；
2. 如果上述划分的右子树节点的值如果有小于根节点的值，则不是后序遍历序列；
3. 在左子树和右子树中分别递归。
# -*- coding:utf-8 -*-class Solution:def VerifySquenceOfBST(self, sequence):# write code here# print(sequence)n=len(sequence)index=0leftsequence=[]rightsequence=[]if n==0:return Falsefor i in range(n):if sequence[i]>sequence[-1]:leftsequence=sequence[:i] #该值的左侧为左子树rightsequence=sequence[i:-1] #该值及其的右侧去除最后节点可先默认全部为右子树index=i #序列中第一个比根节点大的值value并保存其索引breakfor j in rightsequence: #如果右子树中有小于根节点的值，则不是后序遍历序列if j<sequence[-1]:return FalseleftTree=TruerightTree=Trueif len(sequence[:index])>0:leftTree=self.VerifySquenceOfBST(sequence[0:index]) #左子树是否为二叉搜索树if len(sequence[index:-1])>0:rightTree=self.VerifySquenceOfBST(sequence[index:-1]) #右子树是否为二叉搜索树#print(leftTree , rightTree)return leftTree and rightTree
测试：
s=Solution()a=[1,3,2,5,7,6,4]print(s.VerifySquenceOfBST(a))b=[1,3,2,7,5,6,4]print(s.VerifySquenceOfBST(b))#result：TrueFalse
转载请注明：XAMPP中文组官网 » python题目代码实现_二叉搜索树的后序遍历序列