#60 Поиск эквивалентных поддеревьев по множеству букв

Компании:
Яндекс
Темы:
АлгоритмыДеревьяПрактика

Дано бинарное дерево с выделенным корнем, в каждой вершине которого записано по одной букве A-Z. Две вершины считаются эквивалентными, если поддеревья этих вершин содержат одинаковое множество (т.е. без учета частот) букв. Нужно найти любую пару эквивалентных вершин:

/*
             A
           /   \
          C     B
         / \   / \
        A   D A   D
       /           \
      B             C
*/
class TNode {
    char value = '\0'; // [A-Z]
    TNode left = null;
    TNode right = null;
};

Pair<TNode, TNode> findEquivalentSubtrees(TNode root) {
    ...
}

Разбор вопроса

Ментор
Ответь как на реальном собеседовании. Я задам уточняющие вопросы, а затем сравню твой ответ с эталонным и покажу точность в %.
Войди, чтобы начать диалог Ментор ведёт диалог по текущему вопросу и учитывает предыдущие сообщения.
Войти