Überprüfen Sie, ob Baum 0 oder 2 Kinder hat

Question

Wie überprüfe ich, ob der gesamte Baum semi-perfekt 0 oder 2 Knoten hat? Berücksichtigen Sie die folgenden Bedingungen:

• Ein Knoten mit 0 Kindern ist halb perfekt.
• Ein Knoten mit 1 Kind ist nicht halb perfekt.
• Ein Knoten mit 2 Kindern ist halb perfekt, wenn (Größe-of-größer-Kind < = size-of-kleiner-Kind * 3)

Das ist, was ich bisher habe:

public static boolean isLeafOrHasTwoChildren(Node t) { 
    if (t.left == null && t.right == null) { 
     return true; 
    } 

    if (t.left == null || t.right == null) { 
     return false; 
    } 
    // Recurse down the tree 
    return isLeafOrHasTwoChildren(t.left) 
     && isLeafOrHasTwoChildren(t.right); 
} 

Größe berechnet die Anzahl der Knoten im Baum.

Answer 1

Lassen Sie uns unsere Bedingungen aufzählen.

• Sie geben "true" zurück, wenn alle besuchten Knoten null sind.
• Sie geben true zurück, wenn alle besuchten Knoten definiert sind.
• Sie geben andernfalls false zurück.

Lassen Sie uns die erste Bedingung identifizieren - isLeaf - wie:

boolean isLeaf = t.left == null && t.right == null; 

die definieren lassen hasAllChildren als:

boolean hasAllChildren = !(t.left == null || t.right == null); 

Wenn wir genau hinsehen, !(t.left == null || t.right == null) das gleiche aufgrund DeMorgans Gesetz als t.left == null && t.right != null ist . Dies erlaubt uns, dies ziemlich geradlinig auszudrücken, und dies ist wahrscheinlich das Stück, das Sie vermissen.

Jetzt diskutieren wir rekursive Strömung. Wir wollen die gesamte Kette von Knoten in einer Besuch-links-rechts-Art durchlaufen. Also, wir wollen unsere Bedingungen überprüfen, bevor wir rekrutieren.

Basisfall: Wenn wir kein Blatt sind (was bedeutet, dass wir nicht alle Kinder haben), geben wir sofort false zurück.

Rekursiver Schritt: Wenn wir ein Blatt sind oder alle Kinder haben, setzen wir die Kette fort.

Lassen Sie uns versuchen, dies auszudrücken.

public static boolean isLeafOrHasTwoChildren(Node t) { 
    // Trivial case; if we have an undefined node, we've definitely reached a leaf. 
    if (t == null) { 
     return true; 
    } 

    boolean isLeaf = t.left == null && t.right == null; 
    boolean hasAllChildren = !(t.left == null || t.right == null); 

    if(isLeaf || hasAllChildren) { 
     return isLeafOrHasTwoChildren(t.left) && isLeafOrHasTwoChildren(t.right); 
    } else { 
     return false; 
    } 
}