我正在尝试解决二叉搜索树问题,但我无法通过所有测试用例 . 如果树是二叉搜索树,我需要返回true,否则,我需要返回false . 我还需要检查重复项并确保右树中的每个值都大于根,并且左树中的每个值都小于根 .
这是我想要解决的黑客挑战,链接在这里:https://www.hackerrank.com/challenges/ctci-is-binary-search-tree
正如我在第一个问题中所建议的那样,Is tree a binary search tree?这是一个解决方案,它不检查重复项,或者右树中的每个值是否大于根,对左侧树也是如此 .
对于重复项,我有一个想法如何解决它,但不知道如何检查值是否小于左侧树上的根,右侧树上是否更大 .
'''
class node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
'''
def checkBST(root):
if root == None or (root.left == None and root.right == None):
return True
elif root.right == None:
return root.left.data < root.data and checkBST(root.left)
elif root.left == None:
return root.right.data >= root.data and checkBST(root.right)
return checkBST(root.left) and checkBST(root.right)
1 回答
Clear, concise and efficient JAVA code :如果您真正了解这种现象,递归很酷 . 我们的想法是验证树的每个节点,使其始终在最小值和最大值之间 . 以 Integer.MIN_VALUE 和 Integer.MAX_VALUE 作为min和max的初始输入开始 .
你也可以尝试一下 .
现在执行此操作以运行该方法 .