SeniorКодРедкоЕщё не отвечали
Найти два поддерева с одинаковым множеством букв за O(N)
В каждой вершине бинарного дерева записана одна буква A–Z. Две вершины эквивалентны, если множества букв в их поддеревьях совпадают (семантика множеств, частоты не учитываются). Верните любые две различные эквивалентные вершины или нулевые указатели, если их нет.
Требования:
- O(N) по времени на дереве из N вершин.
- Алфавит из 26 букв помещается в 32-битную маску, поэтому множество букв поддерева — это OR масок его детей.
struct TNode { char Value; TNode* Left; TNode* Right; };
std::pair<TNode*, TNode*> FindEquivalentSubtrees(TNode* root) {
// ваш код здесь
}Допишите реализацию.
Рекурсия в post-order: множество букв вершины — это (1 << (Value-'A')) в OR с масками детей. Каждую вычисленную маску кладём в хеш-таблицу «маска → вершина»; при первом повторе маски найдены две эквивалентные вершины. Один обход, O(N) время и O(N) память.
- ✗Считать частоты букв вместо трактовки поддерева как множества (спецификация игнорирует частоты)
- ✗Пересчитывать маску поддерева с нуля в каждой вершине вместо OR масок детей
- ✗Забыть добавить букву самой вершины в её маску
- →Как вместо этого вернуть эквивалентную пару с наибольшим суммарным размером поддеревьев?
- →Почему 32-битного целого достаточно и когда понадобился бы другой дескриптор?
Оглавление
Задача
В каждой вершине дерева записана буква A–Z. Найдите две вершины, поддеревья которых содержат одинаковое множество букв.
Решение
#include <unordered_map>
#include <cstdint>
#include <utility>
struct TNode { char Value; TNode* Left; TNode* Right; };
static std::pair<TNode*, TNode*> found{nullptr, nullptr};
uint32_t collect(TNode* node, std::unordered_map<uint32_t, TNode*>& seen) {
if (!node) return 0;
uint32_t mask = 1u << (node->Value - 'A');
mask |= collect(node->Left, seen);
mask |= collect(node->Right, seen);
auto it = seen.find(mask);
if (it != seen.end() && !found.first) found = {it->second, node};
else seen.emplace(mask, node);
return mask;
}
std::pair<TNode*, TNode*> FindEquivalentSubtrees(TNode* root) {
std::unordered_map<uint32_t, TNode*> seen;
found = {nullptr, nullptr};
collect(root, seen);
return found;
}Ключевые моменты
- Множество букв — это битовая маска; объединение поддеревьев — это
ORмасок детей. - Хеш-таблица «маска → вершина» ловит первый повтор за O(N).
- Семантика множеств: частоты не важны, поэтому маска точна.
Оглавление
