Нахождение ближайшего общего предка в иерархии экранов

Условие

Необходимо реализовать вспомогательную функцию firstCommonParent, которая принимает два узла‑экрана, расположенных в общей иерархии, и возвращает их ближайшего общего предка. Функция используется в механизме роутинга: сначала происходит откат (pop) до найденного предка, а затем переход (push) к целевому экрану.

class Screen(
    var parent: Screen? = null,
    var children: List<Screen> = emptyList()
)

fun firstCommonParent(nodeA: Screen, nodeB: Screen): Screen? {
    ...
}

Примеры вызовов:

• firstCommonParent(C, H) → A
• firstCommonParent(C, G) → D
• firstCommonParent(H, D) → D
• firstCommonParent(G, F) → A
• firstCommonParent(C, L) → null

Ответ

Запишите всех предков первого узла, включая его самого, затем поднимайтесь от второго до первого совпадения. Если общих узлов нет, верните null.

Для дерева без циклов и обычного класса Screen из условия:

fun firstCommonParent(nodeA: Screen, nodeB: Screen): Screen? {
    val ancestors = HashSet<Screen>()
    var current: Screen? = nodeA
    while (current != null) {
        ancestors.add(current)
        current = current.parent
    }
    current = nodeB
    while (current != null) {
        if (current in ancestors) return current
        current = current.parent
    }
    return null
}

Время O(hA + hB), память O(hA). Узел считается своим предком, как требует пример H, D → D. Если equals у Screen позже станет структурным, для поиска именно того же узла потребуется множество по ссылочной идентичности.