🔒Открыть пост
и посмотреть медиа
и посмотреть медиа
Задача: 652. Find Duplicate Subtrees
Сложность: medium
Если задан корень бинарного дерева, верните все дублирующие поддеревья. Для каждого вида дублирующих поддеревьев достаточно вернуть корневой узел любого из них. Два дерева являются дублирующими, если они имеют одинаковую структуру с одинаковыми значениями узлов.
Пример:
Input: root = [1,2,3,4,null,2,4,null,null,4]
Output: [[2,4],[4]]
👨💻 Алгоритм:
1⃣Выполните обход дерева и используйте сериализацию для представления каждого поддерева.
2⃣Храните все сериализованные представления поддеревьев в хэш-таблице и отслеживайте частоту их появления.
3⃣Найдите поддеревья, которые появляются более одного раза, и верните корневые узлы этих поддеревьев.
😎 Решение:
function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
}
var findDuplicateSubtrees = function(root) {
const count = new Map();
const result = [];
const serialize = (node) => {
if (!node) return "#";
const serial = `${node.val},${serialize(node.left)},${serialize(node.right)}`;
count.set(serial, (count.get(serial) || 0) + 1);
if (count.get(serial) === 2) {
result.push(node);
}
return serial;
};
serialize(root);
return result;
};
Ставь 👍 и забирай 📚 Базу знаний
