二叉树搜索Chech算法Python不工作

Question

我写这个算法是为了在HackerRank上进行编码挑战，以确定给定的二叉树是否是BST。然而，在某些情况下，当树不是BST时，我的算法返回True。我找不到哪里出了问题，一切似乎都很好，对吗？还是关于BST有什么我不知道的

节点定义为：

class node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

我的算法是

def checkBST(root):
    if not root:
        return True
    else:
        if root.left and root.left.data >= root.data:
                return False
        if root.right and root.right.data <= root.data:
                return False
    return checkBST(root.left) and checkBST(root.right)

Answer 1

请看下面的图片，您的代码给出了错误的答案：

你错在哪里：

1。如果左子树上存在元素，如果存在值大于root的节点

2.如果右子树上存在元素，如果存在值小于root的节点

您应该尝试以下方法：

if not root:
    return True
else:
    if root.left and maximumOfSubtree(root.left) >= root.data:
            return False
    if root.right and minimumOfSubtree(root.right) <= root.data:
            return False
return checkBST(root.left) and checkBST(root.right)

Answer 2

二叉搜索树的左分支上的all节点小于父节点，右分支上的all节点大于父节点

因此，您的代码在以下情况下失败：

      5
     / \
    4   7
   / \
  2   6

它不是一个有效的BST，因为如果搜索6，您将从根开始跟随正确的分支，然后无法找到它

Answer 3

因此，问题在于确定给定的树是否为BST。
最好的方法是通过顺序遍历来发现

• 按顺序遍历给定的树并将结果存储在临时数组中
• 检查临时数组是否按升序排序，如果是，则树为BST

这可能是一种方法

def check_binary_search_tree_(root):
    visited = []
    def traverse(node):     
        if node.left:   traverse(node.left)
        visited.append(node.data)
        if node.right:  traverse(node.right)
    traverse(root)

    fc = {}
    for i in visited:
        if i in fc:
           return False
        else:
            fc[i]=1

    m = sorted(visited)
    if visited==m:
        return True
    return False

有关其他方法https://www.geeksforgeeks.org/a-program-to-check-if-a-binary-tree-is-bst-or-not/
方法1和方法2与您的方法相似，因此它也将帮助您理解这一点