/* Ο μικρότερος κοινός πρόγονος σε δέντρο σε O(1) μνήμη Περιγραφή Δίνεται ένα δυαδικό δέντρο (όχι δέντρο αναζήτησης): struct Node { Node* parent; Node* left; Node* right; } Πρέπει να γράψετε μια συνάρτηση που, για δύο δοθέντα κόμβους, θα επιστρέφει τον μικρότερο (πιο κοντινό) κοινό πρόγονο: Node* Lca (Node* a, Node* b); */

Για να βρείτε τον πλησιέστερο κοινό πρόγονο (LCA) σε ένα δυαδικό δέντρο με δείκτες προς τους γονείς και χωρίς επιπλέον μνήμη, μπορείτε να χρησιμοποιήσετε την ακόλουθη προσέγγιση:

1. Υπολογίστε το βάθος κάθε ενός από τα δύο κορυφαία σημεία.
2. Ανυψώστε το βαθύτερο κορυφαίο σημείο προς τα πάνω κατά μήκος της αλυσίδας των γονέων μέχρι τα βάθη να γίνουν ίσα.
3. Στη συνέχεια, ανεβείτε ταυτόχρονα κατά μήκος των αλυσίδων των γονέων και των δύο κορυφαίων σημείων μέχρι να συναντηθούν — αυτό θα είναι το LCA.

Παράδειγμα σε Go:

type Node struct {
    parent *Node
    left   *Node
    right  *Node
}

func depth(n *Node) int {
    d := 0
    for n != nil {
        n = n.parent
        d++
    }
    return d
}

func Lca(a, b *Node) *Node {
    da := depth(a)
    db := depth(b)

    // Ανυψώστε τον βαθύτερο κόμβο
    for da > db {
        a = a.parent
        da--
    }
    for db > da {
        b = b.parent
        db--
    }

    // Ανεβείτε μαζί μέχρι να βρείτε τον κοινό πρόγονο
    for a != b {
        a = a.parent
        b = b.parent
    }
    return a
}

Αυτός ο αλγόριθμος χρησιμοποιεί μόνο δείκτες και σταθερή μνήμη, λειτουργεί σε χρόνο O(h), όπου h είναι το ύψος του δέντρου.