symmetrischer Baumalgorithmus (Invert + gleicher Baum)

Question

Bei einem binären Baum prüfen, ob es ein Spiegel von sich selbst ist (dh symmetrisch um sein Zentrum).

Es ist eine Frage zu Leetcode. Was ich tue ist, den Baum zu invertieren und dann zu vergleichen, ob der umgekehrte Baum derselbe wie der ursprüngliche Baum ist. Aber ich kann den Testfall nicht bestehen. Mein Code ist wie folgt, kann mir jemand einen Vorschlag geben? Vielen Dank.

Klasse Solution (Objekt):

def isSymmetric(self, root): 
    node = self.invert(root) 
    def dfs(root, node): 
     if not root and not node: 
      return True 
     if not root or not node: 
      return False 
     if root.val == node.val and dfs(root.left, node.left) and dfs(root.right, node.right): 
      return True 
     else: 
      return False 

    return dfs(root, node) 


def invert(self, node): 
    if node: 
     node.left, node.right = self.invert(node.right), self.invert(node.left) 
    return node 

Answer 1

Es sieht aus wie viel Arbeit zu invertieren und zu validieren. Sie können versuchen, den Baum zu drucken und den Rückgabewert bei jedem Schritt zu verfolgen. Meine Vermutung ist, dass es keine Zeit mehr hat, da es zusätzliche Operationen gibt.

Oder

Sie können durch den Baum Rekursion und prüfen, ob für jeden Knoten links und rechts Spiel.

Beispiel:

def isSymmetric(self, root) 
    #single node or no node 
    if root == null : 
     return false 

    else : 
     return dfs(root) 

def dfs(root): 
    #single node 
    if(root.left == null and root.right == null): 
     return true 

    #both childs exist 
    if(root.left != null and root.right != null): 
     return (dfs(root.left) & dfs(root.right)) 

    #Asymmetric 
    else : 
     return false