python - 黑客排名 : Check Binary Search Tree: Python -test case -for duplications

Question

与 HackerRAank 相关的问题 -“树:这是二叉搜索树吗？” https://www.hackerrank.com/challenges/ctci-is-binary-search-tree/problem

挑战是检查给定的树是否是二叉搜索树条件:左节点的数据将小于根，右节点的数据将大于根，值不能等于根。树不能包含重复项代码:

def check( root, min_number ,max_number):
    if root == None or (root.left == None and root.right == None): #Check empty tree
        return True
    elif root.data <= root.left.data or root.right.data <= root.data: #+Check dup
        return False
    elif root.data <= int(min_number) or root.data >= int(max_number):
        return False
    elif root.right == None:
        return root.left.data < root.data and check(root.left)
    elif root.left == None:
         return root.right.data > root.data and check(root.right)
    else:
        return check(root.left, int(min_number), root.data) and check(root.right, root.data, int(max_number))

def checkBST(root):
    return check(root,0,10000)# const given

并非所有重复项都会被捕获。

测试用例(这只是一个示例):

2
1 2 3 4 6 8 10 11 12 13 14 15 16 16 18 19 21 21 22 23 24 25 26 27 78

答案应该是“否”

对于我错过了哪些条件/需要调整什么有什么建议吗？

Answer 1

我认为你做得太多，同时做得太少。考虑这个片段:

elif root.data <= root.left.data or root.right.data <= root.data: #+Check dup
    return False

现在考虑这个:

else:
    return check(root.left, int(min_number), root.data) and check(root.right, root.data, int(max_number))

如果您要在第二个片段中递归，那么为什么需要费心“深入”子级以在第一个片段中进行比较？

此外，为什么您偶尔会尝试将数字转换为 int？您对它们一开始就是整数感到满意吗？

我建议您减少代码量 - 摆脱不需要的 int() 强制，并摆脱多余的测试。相反，仅关注当前节点。最后，做出选择 - 您使用的是 <= 和 >= 还是 < 和 > 比较？对所有测试都这样做，并确保适当调整参数。如果传入的最小值和最大值是包含参数，则使用 <= 和 >=，并确保在递归时加或减 1。