Zähle die Gesamtzahl der Kanten im Binärbaum

Question

Ich muss eine Methode schreiben, um die Gesamtzahl der Kanten in einem Binärbaum zu berechnen. Ich habe Rekursion versucht, weil sie basierend auf der Anzahl der Knoten - 1 berechnet werden kann, aber nicht sicher war, wie man am Ende der Rekursion eins subtrahiert. Aus diesem Grund versuche ich, eine Variable "count" zu aktualisieren und am Ende nur eins zu subtrahieren. Ich habe mich gefragt, ob das der beste Ansatz ist oder ob ich es anders versuchen sollte.

public int numOfEdges(Node v){ 
    int count; 
    if(isLeaf(v){ 
     count = 0; 
    } 
    else{ 
     count = 1 + numOfEdges(left(v)) + numOfEdges(right(v)); 
    } 
    return count - 1; 
} 

Answer 1

ich denke, das am einfachsten sein könnte nur durch das Schreiben zwei verschiedene Methoden, eine übliche Technik, wenn Rekursion zu erreichen:

private int numNodesIn(Node v) { 
    if (v == null) return 0; 
    return 1 + numNodesIn(v.left) + numNodesIn(v.right); 
} 

public int numEdgesIn(Node v) { 
    return v == null? 0 : numNodesIn(v) - 1; 
}