obsidian/АиСД/Задачи/LeetCode/Lowest Common Ancestor of a Binary Tree III.md

Leetcode #1650 | #Medium | Деревья | BST | Математика

Идея

Отличие от Lowest Common Ancestor of a Binary Tree - нам не дают корень. В чем логика. Пусть путь от p до общего предка - A, от q - B, часть от предка до null (выход за корень) - C. Когда указатель от p доходит до null мы скидываем его в q, для q делаем такое же, только скидываем до p. А теперь посчитаем пути.
a - A + C + B
b - B + C + A
Вот и все

Big-O

• Время O(N)
• Память O(1)

Код

class Solution {
    public Node lowestCommonAncestor(Node p, Node q) {
        Node a = p, b = q;
        while (a != b) {
            a = (a == null) ? q : a.parent;
            b = (b == null) ? p : b.parent;
        }
        return a;
    }
}