输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

Solutions

规律转化成代码的能力还值得练练啊……注意这里注释掉的做法是不合适的,因为有可能第一个 for 循环都不执行!!!!这样的话 split_i 就还是0,此时不应该0,而是遍历到最后了!

# -*- coding:utf-8 -*-
class Solution:
    def VerifySquenceOfBST(self, sequence):
        # write code here
        if sequence is None or len(sequence)<=0:
            return False
        root = sequence[-1]
        split_i = 0
        # for i in range(len(sequence)-1):
        #     if sequence[i] > root:
        #         print 'up', i
        #         split_i = i
        #         break
        # print 'split_i', split_i, 'sequence size', len(sequence)
        # for i in range(split_i, len(sequence)-1):
        #     if sequence[i] < root:
        #         print 'below', i
        #         return False
        for node in sequence[:-1]:
            if node > root:
                break
            split_i += 1
        for node in sequence[split_i:-1]:
            if node < root:
                return False
        left = True
        if split_i > 0:
            left = self.VerifySquenceOfBST(sequence[:split_i])
        right = True
        if split_i < len(sequence)-1:
            right = self.VerifySquenceOfBST(sequence[split_i:len(sequence)-1])
        return left and right

References

  1. 从上往下打印二叉树