Kürzeste Root Blattpfad

Question

Was ist der einfachste Weg, vorzugsweise Rekursion, den kürzesten Wurzel bis zum Blatt finden Weg in einem BST (binärer Suchbaum). Java bevorzugt, Pseudo-Code in Ordnung.

Danke!

Answer 1

Allgemeine Beschreibung:

Verwenden Sie eine Breitensuche (BFS) als zu einem Tiefensuche (DFS) . Finden Sie den ersten Knoten ohne Kinder.

eine DFS verwenden Sie möglicherweise auf einige Eingangs Bäume Glück (aber es gibt keine Möglichkeit, das Glück zu kennen gelernt haben, so dass Sie immer noch den ganzen Baum suchen müssen), aber die BFS-Methode ist viel schneller und Sie können eine Lösung finden ohne alle Knoten zu berühren.

Um die Wurzel zu Blatt Weg zu finden, könnten Sie dem ersten gefunden kinderlos Knoten der ganzen Weg zurückverfolgen bis zur Wurzel der Mutter Referenz. Wenn Sie keine übergeordnete Referenz in jedem Knoten gespeichert haben, können Sie den Überblick über die übergeordneten Knoten halten, wie Sie rekursiv. Wenn Sie Ihre Liste in umgekehrter Reihenfolge haben Sie könnten alles auf einem Stapel schieben und es dann aus Pop.

Pseudo-Code:

Das Problem ist sehr einfach; hier ist Pseudo-Code die kleinste Länge zu finden:

1. Setzen Sie den Wurzelknoten in der Warteschlange.

Wiederholen, während die Warteschlange nicht leer ist, und kein Ergebnis gefunden wurde:

2. Ziehen Sie einen Knoten aus dem Anfang der Warteschlange und überprüfen, ob es keine Kinder hat. Wenn es keine Kinder Sie sind fertig Sie den kürzesten Weg gefunden.
3. Ansonsten drücken alle Kinder (links, rechts) in die Warteschlange.

Finden aller kürzesten Pfade:

Um alle kürzesten Pfade finden Sie die Tiefe des Knotens zusammen mit Knoten in der Warteschlange speichern. Dann würden Sie den Algorithmus für alle Knoten in der Warteschlange mit der gleichen Tiefe fortgesetzt werden.

Alternative:

Wenn Sie stattdessen eine DFS zu verwenden, entschieden, würden Sie den gesamten Baum suchen, um den kürzesten Weg zu finden. Dies könnte sich aber so weit, indem sie einen Wert für die kürzeste optimiert werden, und die Überprüfung nur die Tiefe der Zukunft Knoten, bis Sie eine neue kürzeste finden, oder bis Sie erreichen die kürzeste bisher. Das BFS ist eine viel bessere Lösung though.

Answer 2

Dies ist in C ++, aber es ist so einfach, dass man es kann leicht umwandeln. Ändern Sie einfach min bis max die maximale Baumtiefe zu erhalten.

int TreeDepth(Node* p)
{
    return (p == NULL) ? 0 : min(TreeDepth(p->LeftChild), TreeDepth(p->RightChild)) + 1;
}

Nur um zu erklären, was dies zu tun, wird es aus dem Blattknoten zu zählen (es gibt 0 zurück, wenn er ein Blatt findet) und zählt zurück bis zur Wurzel. Dadurch für die linke und rechte Seite des Baumes und unter dem Minimum werden Sie den kürzesten Weg.

Answer 3

Breitensuche ist gerade optimal in Bezug auf die Anzahl von Eckpunkten besucht. Sie haben jedes einen der Eckpunkte besuchen Sie in einer Breitensuche nur, um Ihnen die nächste Blatt zu beweisen, besuchen würde!

Wenn Sie jedoch ein Mandat haben Rekursion zu verwenden, Ansatz Mike Thompson ist fast die richtige zu verwenden - und ist etwas einfacher

.

TD(p) is
  0 if p is NULL (empty tree special case)
  1 if p is a leaf (p->left == NULL and p->right == NULL)
  min(TD(p->left), TD(p->right)) if p is not a leaf 

Answer 4

static int findCheapestPathSimple (TreeNode root) {

if(root==null){
    return 0; 
}

return root.data+Math.min(findCheapestPathSimple(root.left), findCheapestPathSimple(root.right));

}