Знайти загального предка для двух вузлів дерева

Задача

Написати функцію яка для вказаного дерева і двох його елементів знаходить найблищого до цих елементів предка.

Дерево не є бінарним деревом пошуку.

Рішення

Для поточного елемента дерева (починаємо з корня) перевіряємо чи елементи обоє знаходяться у лівому/правому піддереві і якщо так то рекурсивно продовжуємо пошук у відповідному піддереві. Інакше поточний елемент є предком.

bool covers(tree *root, tree *p) { if (!root) return false; if (root == p) return true; return covers(root->left, p) || covers(root->right, p); } tree* common_ancestor(tree *root, tree *p, tree *q) { if (covers(root->left, p) && covers(root->left, q)) return common_ancestor(root->left, p, q); if (covers(root->right, p) && covers(root->right, q)) return common_ancestor(root->right, p, q); return root; }

Залишити відповідь