判断一棵满二叉树是否为二叉搜索树

题目描述：

给定一棵满二叉树，判定该树是否为二叉搜索树，是的话打印 True，不是的话打印 False。

说明：

a. 二叉搜索树（Binary Search Tree），它或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉搜索树。
b. 满二叉树，除最后一层无任何子节点外，每一层上的所有结点都有两个子结点二叉树
c. 树内节点数不超过 10000，非空节点值为大于 0 小于 65536 的整数，空树或空节点输入为 None

输入描述:

从根节点开始，逐层输入每个节点的值，空树或空节点输入为 None
比如：10,5,15,3,7,13,18

输出描述:

是二叉搜索树的话打印 True，不是的话打印 False

示例1

输入
10,5,15,3,7,13,18

输出
True

解题思路：

1、先处理输入数据，将输入保存在列表 list 中，注意要将字符数字转化为整数数字， 'None' 转化为 None；
2、定义树结构，根据 list 递归构造这棵满二叉树；
3、判断这棵满二叉树是否为二叉搜索树（BST）。

第 1 步很好做，循环处理一下即可；
第 2 步，根据满二叉树的性质，如果根的下标为 i，则左孩子为 2*i，右孩子为 2*i+1，利用这个性质可以进行递归构造这棵二叉树；
这道题的难点在于第 3 步，即如何判断一棵树为 BST 呢？刚开始我写出了这样的代码：

    def judgeBST(self, root):
        if not root:
            return True
        if root.left and root.left.val > root.val:
            return False
        if root.left and root.right.val < root.val:
            return False
        return self.judgeBST(root.left) and self.judgeBST(root.right)

但是，最终通过了 90%，有一个 case 没有通过：10,5,15,3,11,13,18，把它画成满二叉树之后，它不是 BST，应该返回 False，但是上面这个代码返回了 True。分析原因发现，上述代码只能判断每棵子树满足 BST 的条件，但是全局 BST 可能就不满足了（11 > 10）。具体的错误原因可以参考下面这篇博客，写得很清楚：

判断一棵树是否是二叉搜索树

实际上，我们可以利用 BST 的性质：中序遍历是递增的 进行判断。

使用中序遍历的方法实现：

对树进行中序遍历，将结果保存在 temp 数组中；
检测 temp 数组是否为升序排列，如果是，则为 BST，反之则不是。

此方法还可以进一步的优化，不用 temp 数组，避免使用额外的内存开销。在中序遍历时使用一个全局变量 pre 保存前驱节点，如果当前节点的值小于前驱节点的值 pre.val，则该树不是 BST。

完整代码 Python3 实现：

class TreeNode:    # 定义树结构
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    
    def _input(self):    # 处理输入
        li = []
        for num in input().split(','):
            if num == 'None':
                li.append(None)
            else:
                li.append(int(num))
        return [0] + li    # 下标从 1 开始，便于接下来二叉树的构造
    
    def construct(self, li, pos):    # 根据列表 li 递归构造二叉树，pos 为 li 的索引位置
        if pos >= len(li) or li[pos] == None:
            return None
        node = TreeNode(li[pos])
        node.left = self.construct(li, 2*pos)
        node.right = self.construct(li, 2*pos+1)
        return node
    
    def judgeBST(self, root):    # 利用 BST 中序遍历递增的性质判断是否为 BST
        if not root:
            return True
        if not self.judgeBST(root.left):
            return False
        if self.pre != None and self.pre.val > root.val:
            return False
        self.pre = root
        if not self.judgeBST(root.right):
            return False
        return True
    
    def ans(self):    # 返回结果
        li = self._input()
        root = self.construct(li, 1)
        self.pre = None    # 全局遍历 self.pre，保存树的前驱结点
        return self.judgeBST(root)

print(Solution().ans())    # 调用函数，输出结果

最后编辑于：2019.10.29 17:27:46