Сложность: medium
Если задан корень бинарного дерева, верните все дублирующие поддеревья. Для каждого вида дублирующих поддеревьев достаточно вернуть корневой узел любого из них. Два дерева являются дублирующими, если они имеют одинаковую структуру с одинаковыми значениями узлов.
Пример:
Input: root = [1,2,3,4,null,2,4,null,null,4]
Output: [[2,4],[4]]
👨💻 Алгоритм:
1⃣Выполните обход дерева и используйте сериализацию для представления каждого поддерева.
2⃣Храните все сериализованные представления поддеревьев в хэш-таблице и отслеживайте частоту их появления.
3⃣Найдите поддеревья, которые появляются более одного раза, и верните корневые узлы этих поддеревьев.
😎 Решение:
public class TreeNode {
public var val: Int
public var left: TreeNode?
public var right: TreeNode?
public init(_ val: Int) {
self.val = val
self.left = nil
self.right = nil
}
}
func findDuplicateSubtrees(_ root: TreeNode?) -> [TreeNode?] {
var count = [String: Int]()
var result = [TreeNode?]()
@discardableResult
func serialize(_ node: TreeNode?) -> String {
guard let node = node else { return "#" }
let serial = "\(node.val),\(serialize(node.left)),\(serialize(node.right))"
count[serial, default: 0] += 1
if count[serial] == 2 {
result.append(node)
}
return serial
}
serialize(root)
return result
}Ставь 👍 и забирай 📚 Базу знаний