1. Задача: Данное бинарное дерево (не поиска). Узлы содержат указатели на родителя и на потомков (left, right). Нужно написать функцию, которая для двух данных вершин будет возвращать их наименьшего (ближайшего) общего предка. Узел дерева является предком для самого себя, ограничение по памяти O(1).
type Node struct {
parent *Node
left *Node
right *Node
}
func lca(a, b *Node) *Node {
// TODO: implement here
}Ответ
type Node struct {
parent *Node
left *Node
right *Node
}
func depth(x *Node) int {
d := 0
for x != nil {
d++
x = x.parent
}
return d
}
func lca(a, b *Node) *Node {
if a == nil || b == nil {
return nil
}
da :=…