Drzewo binarne tutaj nie musi być drzewem wyszukiwania binarnego.
Strukturę można przyjąć jako -

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

Maksymalne rozwiązanie, które mogłem rozwiązać z przyjacielem, było tego rodzaju -
Rozważaćto drzewo binarne :

Drzewo binarne http://lcm.csa.iisc.ernet.in/dsa/img151.gif

Inorder traversal yields - 8, 4, 9, 2, 5, 1, 6, 3, 7

I plonowanie postorderów - 8, 9, 4, 5, 2, 6, 7, 3, 1

Tak więc, na przykład, jeśli chcemy znaleźć wspólnego przodka węzłów 8 i 5, to tworzymy listę wszystkich węzłów, które są między 8 a 5 w przejściu przez drzewo, które w tym przypadku jest [4, 9 , 2]. Następnie sprawdzamy, który węzeł na tej liście pojawia się jako ostatni w przejściu postorder, czyli 2. Stąd wspólny przodek dla 8 i 5 to 2.

Złożoność tego algorytmu, jak sądzę, to O (n) (O (n) dla przemierzania w trybie inorder / postorder, reszta kroków ponownie to O (n), ponieważ są one niczym więcej niż prostymi iteracjami w tablicach). Ale istnieje duża szansa, że ​​to jest złe. :-)

Ale jest to bardzo prymitywne podejście i nie jestem pewien, czy w jakimś przypadku załamie się. Czy jest jakieś inne (być może bardziej optymalne) rozwiązanie tego problemu?