OJ address
剑指Offer : 二叉搜索树的后序遍历序列
Description
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
Solution in Python
# -*- coding:utf-8 -*-
class Solution:
def VerifySquenceOfBST(self, sequence):
length = len(sequence)
if length == 0:
return False
if length == 1:
return True
str = sequence[-1]
i = 0
while sequence[i] < str:
i+=1
for x in xrange(i, length-1):
if sequence[x] < str:
return False
a = True
b = True
if len(sequence[:i])>0:
a = self.VerifySquenceOfBST(sequence[:i])
if len(sequence[i:length-1])>0:
b = self.VerifySquenceOfBST(sequence[i:length-1])
return a and b
My Idea
知道二叉搜索树的定义就很容易做了
- 根据后序遍历的定义，如果一个序列是二叉树的后续遍历的结果，那么我们不难得出，序列的最后一个节点必定是二叉树的根节点，除了根节点外，序列中前一部分是二叉树的左子树的节点，后面一部分是二叉树的右子树的节点。
- 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
