/* Դեռահասների ընդհանուր նախնին՝ O(1) հիշողությամբ Նկարագրություն Տրված է բինար ծառ (չէ որոնումային). struct Node { Node* parent; Node* left; Node* right; } Պետք է գրել ֆունկցիա, որը երկու տրված հանգույցների համար կվերադարձնի նրանց ամենափոքր (մոտակա) ընդհանուր նախնին: Node* Lca (Node* a, Node* b); */

Երեք ուղղահայաց ծառում, որտեղ կա ծնողների ցուցանիշներ, և առանց լրացուցիչ հիշողության, կարող եք օգտագործել հետևյալ մոտեցումը՝

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 ծառի բարձրությունն է։