与 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
答案应该是“否”
对于我错过了哪些条件/需要调整什么有什么建议吗?
最佳答案
我认为你做得太多,同时做得太少。考虑这个片段:
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。
关于python - 黑客排名 : Check Binary Search Tree: Python -test case -for duplications,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/46651063/