这棵树是二叉搜索树吗？

-2

我想解决一个二叉搜索树问题，但我无法通过所有的测试用例。如果树是二叉搜索树，则需要返回true，否则，我需要返回false。我还需要检查重复项，并确保右侧树中的每个值都大于根，并且左侧树中的每个值都小于根。这棵树是二叉搜索树吗？

这是我试图解决hackerrank挑战，链接是在这里：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)

来源

2017-07-03 user2645029

所以你要我们解决这个黑客问题，并给你的代码？ –

[二叉树和二叉搜索树之间的区别]可能的重复（https://stackoverflow.com/questions/6380231/difference-between-binary-tree-and-binary-search-tree） –

我不在乎这是Hackerrank或任何，我试图解决一个二叉搜索树的问题，我尝试了很多迭代，并坚持在左树上检查较小的值，并在右树上更大。我在hackerrank上运行它，因为它们有很好的测试用例。不，这不是重复的https://stackoverflow.com/questions/6380231/difference-between-binary-tree-and-binary-search-tree – user2645029

清晰，简洁，高效的JAVA代码：递归是冷静，如果你真正理解的现象。这个想法是验证树的每个节点，使其始终位于最小值和最大值之间。以开始Integer.MIN_VALUE和Integer.MAX_VALUE作为最小和最大的初始输入。

public boolean isBinarySearch(Node root, int min, int max) { 

    if (root == null) 
     return true; 

    return ((min <= root.val && root.val <= max) && (isBinarySearch(
      root.left, min, root.val) && isBinarySearch(root.right, 
      root.val, max))); 
}

你也可以试试这个。

class Node { 

public Node left; 
public Node right; 
public int val; 

public Node(int val) { 
    this.val = val; 
} 
}

现在执行此操作来运行该方法。

Node root2 = new Node(12); 
    root2.left = new Node(7); 
    root2.left.left = new Node(4); 
    root2.left.right = new Node(11); 
    root2.right = new Node(16); 
    root2.right.left = new Node(14); 
    root2.right.right = new Node(18); 
    root2.right.right.left = new Node(17); 

    System.out 
      .println("IsBinary=" 
        + wc.isBinarySearch(root2, Integer.MIN_VALUE, 
          Integer.MAX_VALUE)); 
}

来源

2017-07-14 20:54:34 neeranzan

这棵树是二叉搜索树吗？

回答

相关问题