Ist Baum ein binärer Suchbaum?

Question

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?

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

Answer 1

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.

Answer 2

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

• 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.