2017-07-03 17 views
1

Ich versuche, ein binäres Suchbaumproblem zu lösen, aber ich kann nicht alle Testfälle bestehen. Ich muss true zurückgeben, wenn der Baum ein binärer Suchbaum ist, andernfalls muss ich false zurückgeben. Kann mir jemand sagen, was ich falsch mache?Ist Baum ein binärer Suchbaum?

''' 
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) 
+0

Welche Testfälle passieren Sie nicht? –

+0

warum rufst du 'chckBST (root)' nochmal an, sollte es beim ersten Aufruf vom Testfall selbst richtig sein? Ich denke, rekursive Anrufe sollten nur für links und rechts sein – Yazan

Antwort

3

Sie haben viele redundante if Bedingungen in Ihrem Code. Sie können es wie so vereinfachen:

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) 

Überprüfen Sie zunächst für alle None Bedingungen. Kurzschlüsse in Python garantieren, dass wenn die erste Bedingung False ist, die zweite nicht ausgewertet wird. Auf diese Weise können Sie prägnante Aussagen wie return root.left.data < root.data and checkBST(root.left) schreiben.

Schließlich, falls weder der linke noch der rechte Knoten None sind, tun Sie nicht rufen Sie erneut checkBST(root). Dies führt zu einer unendlichen Rekursion.

+1

@GAURANGVYAS Vielen Dank für das darauf hin. Es gab in der Tat einen Fehler, den ich behoben habe, aber nicht genau das, was du erwähnt hast. Eigentlich entspricht 'root.left! = None' der Bedingung' root.left! = None und (root.right! = None oder root.right == None) 'was ich nicht will. Ich behandle diese Bedingungen getrennt. –

+0

Das macht Sinn, danke @COLDSPEED. Ich habe es im HackerRank versucht, aber von 13 Testfällen übergibt es nur 5 von ihnen. Alle anderen scheitern aus irgendeinem Grund. Zum Beispiel ist einer der versagenden Tests dieser, der false ausgeben sollte: Wurzelknoten: 2, Kinder: 1 2 3 5 4 6 7. Irgendwelche Ideen? Das ist die Herausforderung: https://www.hackerrank.com/challenges/ctci-is-binary-search-tree – user2645029

+0

@ user2645029 Zwei Dinge ...Eine besteht darin, nach Duplikaten zu suchen, und die andere besteht darin, sicherzustellen, dass _jeder_ Wert im rechten Baum größer als der Stamm ist, und ähnlich für den linken (Lösungen für beide liegen außerhalb des Bereichs dieser Frage). –

0

Der Grund, warum Sie einige der Tests nicht bestehen, ist, weil Sie nur eine Ebene tief überprüfen. Zum Beispiel, wenn es einen tree so gibt, dass es einen root.left.right.data>root.data hat, dann wird Ihr Code das nicht fangen. Es gibt eine gute Erklärung here

Aber das Wesentliche ist:

  • Ihr Code wird passieren diese

All left children are smaller and all right children are bigger

  • Aber es wird dieses Hinweis das Recht nicht passieren Kind von 2>root.data

Ich denke, diese Lösung es löst (sorry für eine Python-Frage mit JS-Code zu beantworten, aber ich bin sicher, dass Sie die Idee erhalten):

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; 
} 

Auch Bitte verwenden Sie diesen Code nicht, es verwendet O(n) Speicherplatz, um das Problem zu lösen, und ich bin sicher, dass ich eine effizientere Lösung finden kann, wenn ich etwas Zeit auf die Frage verwende.