Ich versuche ein Problem zu lösen, bei dem ich feststellen muss, ob ein Knoten w auf dem Pfad zwischen Knoten u und Knoten v in einem Baum (nicht notwendigerweise binär) liegt.Wie kann man feststellen, ob Knoten w auf dem Pfad zwischen Knoten u und Knoten v in einem Baum liegt?
beispielsweise den folgenden Baum:
1
2 3
4 5 6 7
Knoten 2 liegt auf dem Pfad vom Knoten 4 bis 7
Eine offensichtliche Lösung wäre, die Eulersche Tour des Baumes zu erhalten, und traverse die Knoten, die zwischen den ersten Vorkommen beider Knoten besucht wurden. Dies wäre jedoch im schlimmsten Fall eine O (n) -Lösung, wobei n die Anzahl der Knoten im Baum ist. Ich habe irgendwo gelesen, dass dies mit LCA (Lowest Common Ahnen) getan werden kann. Wie auch immer, ich kann es nicht verstehen. Könnte mir bitte jemand Rat geben?
Sie möchten einen Rat zum Lernen LCA oder das Problem lösen? Sagen Sie, wenn Sie einen Black Box O (h) -Algorithmus zum Finden von LCA haben, wissen Sie, wie man LCA verwendet, um es zu lösen? – shole
Ich weiß, wie LCA von 2 Knoten im Baum mit Sparse-Tabelle und RMQ zu finden. Ich möchte das in der Post beschriebene Problem lösen. Ich habe gerade gelesen, dass das Problem mit LCA effizient gelöst werden kann. Vielleicht könnte es auch mit anderen Methoden gelöst werden. Aber ich kann nicht verstehen, wie LCA oder andere Methoden dieses Problem lösen könnten. – LanceHAOH
Ich denke, wenn die folgenden beiden Bedingungen erfüllt sind, ist die Antwort ja? lassen x = lca (u, v) 1. lca (w, u) = w oder lca (w, v) = w 2. lca (w, x) = x – shole