這棵樹是二叉搜索樹嗎？

-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

這棵樹是二叉搜索樹嗎？

回答

相關問題