Дано бинарное дерево (не дерево поиска). Каждый узел хранит ссылки на родителя,
левого и правого потомка; у корня Parent == nil. Напишите функцию, которая для
двух узлов одного дерева возвращает их наименьшего (ближайшего) общего предка —
самый глубокий узел, предками которого являются оба. Узел считается предком
самого себя.
type Vertex struct {
Val int
Parent *Vertex
Left *Vertex
Right *Vertex
}
// FindAncestor возвращает ближайшего общего предка a и b.
func FindAncestor(a, b *Vertex) *Vertex
Пример
3
/ \
5 1
/ \ / \
6 2 0 8
/ \
7 4
FindAncestor(5, 1) → 3
FindAncestor(5, 4) → 5 (узел — предок самого себя)
FindAncestor(7, 4) → 2
FindAncestor(6, 6) → 6
Ограничения
a и b не nil и лежат в одном дереве; в дереве до 10⁶ узлов, оно может
быть вырожденным (цепочкой).- Указатели в дереве менять нельзя, даже временно.
- Дополнительная память — O(1): никаких map, слайсов и рекурсии.
Ожидается O(h) по времени, где h — высота дерева.
Разбор и эталонное решение — после своей попытки: на собеседовании подсказок не будет.
Сначала попробуй сам — подсказки не дают готовый ответ.