问题一：
输入一个整数数组，
判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。
假设输入的数组的任意两个数字都互不相同。
正确的后序遍历结果：
sequence = [37, 35, 51, 47, 59, 73, 93, 98, 87, 61]
python源码：
class Solution:
def VerifySquenceOfBST(self, sequence):
# write code here
if sequence == None or len(sequence) == 0:
return False
length = len(sequence)
root = sequence[length - 1] # 在二叉搜索 树中 左子树节点小于根节点 （应该是二叉排序树）
for i in range(length): # 获得左右的分叉口
if sequence[i] > root:
break # 二叉搜索树中右子树的节点都大于根节点
for j in range(i, length):
if sequence[j] < root:
return False # 判断左子树是否为二叉树
left = True
if i > 0:
left = self.VerifySquenceOfBST(sequence[0:i]) # 判断 右子树是否为二叉树
right = True
if i < length - 1:
right = self.VerifySquenceOfBST(sequence[i:-1]) return left and right if __name__ == '__main__':
s = Solution()
# sequence = [37, 35, 51, 47, 59, 73, 93, 98, 61, 87] # 错误的二叉排序树的后续遍历
sequence = [37, 35, 51, 47, 59, 73, 93, 98, 87, 61] # 正确的二叉排序树的后续遍历
print(s.VerifySquenceOfBST(sequence))
问题二：
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None class Solution:
def HasSubtree(self, pRoot1, pRoot2): # 判断是否有子树
if pRoot1 == None or pRoot2 == None:
return False result = False
if pRoot1.val == pRoot2.val: # 根节点相等，进行下一步
result = self.IsSubtree(pRoot1, pRoot2) # 判断子节点是否“相等” if result == False:
res1 = self.HasSubtree(pRoot1.left, pRoot2)
res2 = self.HasSubtree(pRoot1.right, pRoot2)
result = res1 or res2 return result def IsSubtree(self, pRoot1, pRoot2):
if pRoot2 == None:
return True
if pRoot1 == None:
return False
if pRoot1.val == pRoot2.val:
leftt = self.IsSubtree(pRoot1.left, pRoot2.left)
rightt = self.IsSubtree(pRoot1.right, pRoot2.right)
return leftt and rightt
return False def getBSTwithPreTin(self, pre, tin): # 最终确定树的形状，使用object的形式存储
if len(pre) == 0 | len(tin) == 0: # 任何一个为空树，则返回空
return None # 直接跳出代码
root = TreeNode(pre[0]) # 前序遍历直接找到根节点(第一个元素就是根节点)
for i, item in enumerate(tin): # 序号和元素，将中序遍历拆分成左右两支
if root.val == item:
root.left = self.getBSTwithPreTin(pre[1:i + 1], tin[:i])
root.right = self.getBSTwithPreTin(pre[i + 1:], tin[i + 1:])
return root if __name__ == '__main__':
solution = Solution() preorder_seq = [1, 2, 4, 7, 3, 5, 6, 8] # 前序遍历
middleorder_seq = [4, 7, 2, 1, 5, 3, 8, 6] # 中序遍历
treeA = solution.getBSTwithPreTin(preorder_seq, middleorder_seq) preorder_seq = [1, 2, 3]
middleorder_seq = [2, 1, 3]
treeB = solution.getBSTwithPreTin(preorder_seq, middleorder_seq) print(solution.HasSubtree(treeA, treeB))