Визначити чи є одне дерево піддеревом іншого

Задача

Дано два дерева. Перше має дуже великий розмір (міліони елементів), інше – менший (сотні елементів). Треба написати функцію яка буде визначати чи є менше дерево піддеревом більшого.

Рішення 1

Для кожного елемента більшого дерева що містить значення еквівалентне значенню коріневого елемента меншого дерева перевіримо чи всі інші елементи також ідентичні.

 

// визначити чи дерева ідентичні bool match_tree(tree * r1, tree *r2) { if (r1 == NULL && r2 == NULL) return true; if (r1 == NULL || r2 == NULL) return false; if (r1->val != r2->val) return false; return match_tree(r1->left, r2->left) && match_tree(r1->right, r2->right); } // визначити чи другий параметр є піддеревом першого bool is_sub_tree(tree *r1, tree *r2) { if (!r2) return true; if (!r1) return false; if (r1->val == r2->val) return match_tree(r1, r2); return is_sub_tree(r1->left, r2) || is_sub_tree(r1->right, r2); }

Рішення 2

Можна для обох дерев побудувати рядок із значень їх елементів у порядку обхода inplace (лівий під-елемент->батьківський елемент->правий під-елемент). Після цього перевірити чи рядок для другого дерева є підрядком для першого дерева.

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