Der Binärbaum hier muss nicht unbedingt ein binärer Suchbaum sein.
Die Struktur könnte wie folgt verstanden werden:

struct node {
    int data;
    struct node *left;
    struct node *right;
};

Die maximale Lösung, die ich mit einem Freund ausarbeiten konnte, war etwas in dieser Art -
Erwägendieser binäre Baum :

Binärer Baum http://lcm.csa.iisc.ernet.in/dsa/img151.gif

Die Inorder Traversal Ausbeuten - 8, 4, 9, 2, 5, 1, 6, 3, 7

Und der Nachbestellungsdurchlauf ergibt - 8, 9, 4, 5, 2, 6, 7, 3, 1

Wenn wir zum Beispiel den gemeinsamen Vorfahren der Knoten 8 und 5 finden wollen, dann erstellen wir eine Liste aller Knoten, die im Inorder Tree Traversal zwischen 8 und 5 liegen, was in diesem Fall zufällig [4, 9 ist 2]. Dann prüfen wir, welcher Knoten in dieser Liste zuletzt in der Nachbestellungsüberquerung erscheint, nämlich 2. Daher ist der gemeinsame Vorfahr für 8 und 5 2.

Ich glaube, die Komplexität für diesen Algorithmus ist O (n) (O (n) für Inorder- / Postorder-Traversen, der Rest der Schritte ist wiederum O (n), da es sich nur um einfache Iterationen in Arrays handelt.) Es besteht jedoch eine große Wahrscheinlichkeit, dass dies falsch ist. :-)

Aber dies ist eine sehr grobe Herangehensweise, und ich bin nicht sicher, ob sie für einen bestimmten Fall zusammenbricht. Gibt es eine andere (möglicherweise optimalere) Lösung für dieses Problem?