// MARK: - Найти 2 одинаковых поддерева

/*
Нахождение эквивалентных поддеревьев:
для каждой вершины находим множество как объединение
множеств детей и своего значения

Добавляем в словарь, где ключ - множество, а значение список вершин с таким множеством
Если в словаре есть список из двух и более значений, то искомые вершины найдены
*/



func findEquivalentSubtrees(root: Node?) -> (Node?, Node?) {

    var nodesSets = [Set<Character>: [Node]]()

    func findSet(node: Node?) -> Set<Character> {
        var resultSet = Set<Character>()
        guard let node = node else { return resultSet }

        resultSet.insert(node.value)
        resultSet = resultSet.union(findSet(node: node.left))
        resultSet = resultSet.union(findSet(node: node.right))

        nodesSets[resultSet, default: []].append(node)
        return resultSet
    }

    _ = findSet(node: root)

    for value in nodesSets.values {
        if value.count > 1 {
            return (value[0], value[1])
        }
    }
    return (nil, nil)
}