确定完整的二叉树是否为二叉搜索树

给出一棵完整的二叉树，确定该树是否为二叉搜索树，如果为True，则输出True，否则为False.

说明:

从根节点开始，逐层输入每个节点的值，然后将空树或空节点输入为None

例如: 10,5,15,3,7,13,18

如果是二进制搜索树则为True，否则为False

输入

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

输出

是

1. 首先处理输入数据，将输入保存在列表中，注意将字符数转换为整数，并将“无”转换为“无”；

2. 定义树结构并根据列表递归构造完整的二叉树；

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％，并且有一个失败的案例: 10,5,15,3,11,13,18. 将其绘制为完整的二叉树后判断 二叉排序树判断 二叉排序树，它不是BST，应该返回False，但是上面的代码返回了True. 分析其原因，发现上述代码只能判断每个子树都满足BST的条件，但可能无法满足全局BST（11> 10）. 错误的具体原因可以参考以下博客，该博客非常清楚:

实际上，我们可以利用BST的性质: 中阶遍历是递增的.

使用顺序遍历的方法:

可以在不使用temp数组的情况下进一步优化此方法，并避免使用额外的内存开销. 在中间顺序遍历中，全局变量pre用于保存前任节点. 如果当前节点值小于先前节点值pre.val，则树不是BST.

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-279151-1.html