樹是二叉搜索樹嗎？

我想解決二叉搜索樹問題，但我無法通過所有的測試用例。如果樹是二叉搜索樹，則需要返回true，否則，我需要返回false。誰能告訴我我做錯了什麼？樹是二叉搜索樹嗎？

''' 
class node: 
    def __init__(self, data): 
     self.data = data 
     self.left = None 
     self.right = None 
''' 

def checkBST(root): 
    if root.left == None and root.right == None: 
     return True 
    if root == None: 
     return True 
    if root.left != None: 
     if root.left.data < root.data: 
      return True 
    else: 
     return False 
    if root.right != None: 
     if root.right.data > root.data: 
      return True 
     else: 
      return False 
    return chckBST(root.left) and chckBST(root) and chckBST(root.right)

來源

2017-07-03 user2645029

哪些測試用例不是您傳遞的？ –

爲什麼你再次調用'chckBST（root）'，它應該是來自測試用例本身的第一次調用吧？我認爲遞歸調用應該只針對左側和右側 – Yazan

您的代碼中有很多多餘的if條件。你可以這樣簡化它：

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)

首先，檢查所有的None條件。 python中的短路保證，如果第一個條件是False，則不會評估第二個條件。這使您可以撰寫簡潔的陳述，如return root.left.data < root.data and checkBST(root.left)。

最後，如果左側和右側節點都不是None，那麼而不是再次調用checkBST(root)。這導致無限遞歸。

來源

2017-07-03 12:29:51

@GAURANGVYAS謝謝你指出。確實有一個與我相關的錯誤，雖然不完全是你提到的。其實'root.left！= None'將符合條件'root.left！= None和（root.right！= None或root.right == None）'，這是我不想要的。我分開處理這些條件。 –

這很有道理，謝謝@COLDSPEED。我在HackerRank中嘗試過，但在13個測試用例中，只有5個通過。由於某種原因，所有其他人都失敗了。例如，其中一個失敗的測試是應輸出false的測試：根節點：2，子女： 1 2 3 5 4 6 7.任何想法？這是挑戰：https://www.hackerrank.com/challenges/ctci-is-binary-search-tree – user2645029

@ user2645029兩件事...一個是檢查是否有重複，另一個是確保右側樹中的_every_值大於根，左側相似（兩者的解決方案不在此問題的範圍之內）。 –

所以你沒有通過一些測試的原因是因爲你只能檢查一個深度。例如，如果有一個tree，它有一個root.left.right.data>root.data，那麼你的代碼將無法捕捉到。這是一個很好的解釋here

但要點是：

您的代碼將通過這個

但它不會通過這個另行通知子女2>root.data

我覺得這個解決方案解決了它（對不起回答與JS代碼Python的問題，但我敢肯定你會得到的想法）：

function checkBST(root) { 
    let isBST = true; 
    let BSTUtil = r => { 
     let left, right 
     if(r.left) // Bottom out on the left side 
      left = BSTUtil(r.left) 
     if(r.right) // Bottom out on the right side 
      right = BSTUtil(r.right) 

     if(left > r.data) // Compare with parent 
      isBST = false 
     if(right < r.data) // Compare with parent 
      isBST = false 

     // Return MAX from branch 
     if(!left && !right) 
      return r.data 
     else if(!left) 
      return Math.max(right, r.data) 
     else 
      return Math.max(left, right, r.data) 
    } 
    BSTUtil(root) 
    return isBST; 
}

而且，請不要使用此代碼，它使用O(n)空間來解決問題，如果我花時間解決問題，我相信我可以找到更有效的解決方案。

來源

2017-12-05 01:56:18 Grigio

樹是二叉搜索樹嗎？

回答

相關問題