Binärer Suchbaum Rekursion

[Barny]

Hiho!

Ich hänge seit gestern Abend an einer kleinen Aufgabe, welche ich im Rahmen einer Klausurvorbereitung machen wollte.
Vielleicht könnt ihr mir ein wenig weiterhelfen.

Aufgabe:
Und zwar geht es darum, dass ein binärer Suchbaum gegeben ist auf dem gearbeitet werden soll. Die Aufgabenstellung lautet nun, eine Methode zu schreiben, welche die Gesamtzahl der Knoten des Baumes ausgeben soll, falls sich für jeden einzelnen Knoten die Anzahl der Knoten im linken und rechten Teilbaum höchstens um den Wert 1 unterscheiden.
Wenn es mind. einen Knoten gibt, dessen Unterbäume einen größeren Unterschied aufweisen, dann soll der Wert -1 zurückgegeben werden.

Meine Lösung:

public int sizeIfBalanced() {
    	
    	if(isEmpty()) {
    		return(0);
    	}else {
    		
    		int difference = 0;
    		
    		if((!leftChild.isEmpty() && !rightChild.isEmpty())) {
    		difference = (rightChild.content.getContent() - leftChild.content.getContent());
    		}
    		
    		if(difference > 1) {
    			
    			return(-1);
    			
    		}else {
    			return(leftChild.sizeIfBalanced() + rightChild.sizeIfBalanced()+1);
    		}
    		
    		
    	}
    	
    }

Mein Problem:
Meine Lösung funktioniert soweit prima, allerdings immer nur für die jeweiligen Teilbäume. Heißt, dass wenn er im rechten Teilbaum einen größeren unterschied feststellt, dann hört er da auf und gibt -1 zurück, allerdings läuft es im linken Teilbaum weiter. Ich hoffe ihr versteht mich^^

Mein Lösungsansatz bzw. meine Frage:
Im Endeffekt müsste man alle anderen rekursiven Aufrufe einfach überschreiben oder anhalten, falls er einen größeren Unterschied irgendwo feststellt. Allerdings darf ich laut Aufgabenstellung keine neuen Methoden zur Überprüfung anlegen und darf meinen Code nur in den "Else-Block" schreiben. Nun bin ich ein wenig überfragt^^

Ich würde mich sehr über ein paar Antworten freuen.

mfg

Barny

 

[Flown]

Ich nehme mal an das isEmpty() einen Endpunkt unter einem Blatt beschreibt (damit du keine null hast)?

             root
            /     \
       left         right
      /    \       /      \
empty  empty     empty  empty

Wenn ja, dann hier:

public int sizeIfBalanced() {
  if (isEmpty()) {
    return 0;
  } else {
    int leftTree = leftChild.sizeIfBalanced();
    if (leftTree == -1) {
      return -1;
    }
    int rightTree = rightChild.sizeIfBalanced();
    if (rightTree == -1) {
      return -1;
    }

    int difference = Math.abs(leftTree - rightTree);

    if (difference > 1) {
      return -1;
    } else {
      return leftChild.sizeIfBalanced() + rightChild.sizeIfBalanced() + 1;
    }
  }
}

 

[Barny]

Hallo und danke für deine Antwort!

Musste ein wenig rumprobieren bis es funktioniert hatte mit deiner Ergänzung, und letztendlich ist mir dann aufgefallen, dass mein Testbaum nicht richtig war^^ Da hätte ich denke ich ohne dein beitrag noch länger dran gesessen

mfg

Barny