Produkt von allen Knoten außer einem Binärbaum

Question

Nehmen wir an, wir erhalten einen binären Baum mit einer ganzzahligen Ganzzahl, die an jedem Knoten sitzt.Ich suche nach einem effizienten Weg, um jeden Weg von der Wurzel von der Wurzel zu einem Blatt jedes mögliche Produkt mit genau einem Knoten entlassen zu finden.Ich suche nach einer Lösung ohne Abteilungen (d. H. Intenger können Null sein).

Eine Möglichkeit, um dies zu gehen, dachte ich daran Ich kann alle möglichen Teilprodukte an der Wurzel berechnen.Das ist jeder Knoten speichert das Produkt des eindeutigen Pfads vom Wurzel oben diesen Knoten (außer der in diesem bestimmten Wert gespeicherten Ganzzahl).Dann kann ich für jeden Blattknoten den Pfad zum Root-Knoten hinaufgehen, der die Ganzzahlen unterwegs multipliziert.Bei einem bestimmten Knoten, bevor der Knoten in das Produkt ansammelt, kann ich das Produkt mit dem im Knoten gespeicherten Präfixprodukt multiplizieren.

Es fühlt sich an, als würde ich viele redundante Multiplikationen tun, wenn sie jeden Weg von einem Blatt bis zur Wurzel besuchen, da diese Wege möglicherweise viele Knoten teilen.Gibt es einen Weg schneller, um dies zu tun?

Answer 1

Ein einfacher Ansatz: für einen internen Knoten $ x $ , $ p (x) $ Bezeichnen Sie das Produkt der Ganzzahlen auf dem Pfad vom Wurzel auf $ x $ , und lassen Sie $ Q (x) $ < / span> Bezeichnen Sie den Satz von Ganzen, die als Produkt von allen, sondern einer der Ganzzahl auf dem Pfad von der Wurzel auf $ x $ erhältlich sind. Stecken Sie nun den Baum von der Wurzel von der Wurzel bis zu den Blättern, Computing $ P (x) $ und $ q (x) $ für jeden Knoten $ x $ Wie Sie gehen. Beachten Sie, dass Sie $ P (x), q (x) $ von $ P (W), Q (W) berechnen können ) $ , wobei $ W $ der übergeordnete $ x $ ist. .

Die asymptotische Worst-Case-Laufzeit ist $ O (N ^ 2) $ . Kein Algorithmus hat eine bessere asymptotische Laufzeit mit schlechtester Fälle, da es $ \ theta (n ^ 2) $ verschiedene Produkte geben kann Sie müssen mindestens die Laufzeit-Laufzeit mindestens $ \ theta (n ^ 2) $ haben.