Sui Xin's Blog

[剑指Offer]二叉搜索树的后序遍历序列

Posted on In Disqus:

二叉搜索树

二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树），它有下列两种情况：

  1. 空树；
  2. 具有下列性质的二叉树：
    1. 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
    2. 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
    3. 它的左、右子树也分别为二叉排序树。

题目描述

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

解题思路

根据二叉搜索树的特性，左子树<根结点<右子树，而后序遍历为LRN，故序列的最后一个值一定为根节点。前面的序列被根节点分为左子树和右子树，左子树值都比根节点小，右子树值都比根节点大，否则不是二叉搜索树，如此递归即可。

代码

Python(2.7.3)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# -*- coding:utf-8 -*-
class Solution:
    def VerifySquenceOfBST(self, sequence):
        # write code here
        if len(sequence) == 0:
            return False
        elif len(sequence) == 1:
            return True
        elif len(sequence) == 2 and sequence[0] != sequence[-1]:
            return True
        root = sequence[-1]
        for idx, i in enumerate(sequence):
            if i > root:
                break
        s_left = sequence[:idx]
        s_right = sequence[idx:-1]
        for i in s_right:
            if i <= root:
                return False
        if len(s_left) == 0:
            return self.VerifySquenceOfBST(s_right)
        elif len(s_right) == 0:
            return self.VerifySquenceOfBST(s_left)
        return self.VerifySquenceOfBST(s_left) and self.VerifySquenceOfBST(s_right)

运行时间：27ms
占用内存：5728k

参考

https://baike.baidu.com/item/%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91

Related Posts