Дано: задано двоичное дерева поиска (BST) root с дубликатами, вернуть самое частое встречающее значение ноды.
Если таких значений несколько, вернуть их в виде массива в любом порядке.
Свойства BST:
- Левое поддерево узла содержит только узлы с ключами, меньшими или равными ключу узла.
- Правое поддерево узла содержит только узлы с ключами, большими или равными ключу узла.
- левое, и правое поддеревья должны быть деревьями двоичного поиска.
Пример:
Вход: root = [1,null,2,2]
Выход: [2]
Пример 2:
Вход: root = [0]
Выход: [0]
Ограничения:
Количество узлов в дереве находится в диапазоне [1, 104].
-10^5 <= Node.val <= 10^5
Решения Python:
Первичное решение для собеседования. Он прост, легко реализуем, имеет хорошую сложность и демонстрирует понимание двоичных деревьев и хэш-карт. После выполнения этого решения вы должны быть готовы к просьбе предоставить другое решение.
Максимальная частота равна 2, таким образом, мы имеем два режима: 4 и 8.
Мы можем решить эту задачу, собрав частоты всех значений в дереве, найдя максимальную частоту maxFreq, а затем проверив, какие значения имеют частоту maxFreq.
Для подсчета частоты каждого значения мы выполним поиск в глубину (DFS) по дереву с посещением каждого узла. Перед началом DFS мы инициализируем счетчик хэш-карты - словарь. В каждом посещенном узле мы будем обновлять частоту node.val в счетчике.
После завершения DFS (посещения всех узлов) счетчик будет хранить частоты всех значений. Мы сохраним максимальную частоту как maxFreq, затем выполним итерации по всем элементам счетчика и проверим, какие из них имеют частоту, равную maxFreq. Каждый из этих элементов будет содержаться в нашем окончательном ответе.
Алгоритм: Инициализировать счетчик хэш-карты. Создать функцию dfs(node, counter): Если node равен null, выйти из функции. Увеличиваем частоту node.val в счетчике. Вызвать dfs на обоих дочерних узлах с помощью dfs(node.left, counter) и dfs(node.right, counter). Вызвать dfs(root, counter). Найти максимальное значение в счетчике maxFreq. Инициализируем список ответов ans. Итерация по всем парам ключ-значение в счетчике. Если значение равно maxFreq, добавить ключ в ans. Возвращаем ans.
class Solution:
def findMode(self, root: Optional[TreeNode]) -> List[int]:
def dfs(node, counter):
if not node:
return
counter[node.val] += 1
dfs(node.left, counter)
dfs(node.right, counter)
counter = defaultdict(int)
dfs(root, counter)
max_freq = max(counter.values())
ans = []
for key in counter:
if counter[key] == max_freq:
ans.append(key)
return ans
Более подробно, вводим дополнительную функцию dfs с аргументами node(наше дерево) и counter ( наш словарь) . Но словарь не обычный, а defaultdict. Это подкласс обычного словаря, который позволяет задать значение по умолчанию для несуществующих ключей. Если у нас пустое дерево, ничего не возвращаем, если дерево не пустое, то плюсуем к счётчику по текущему значению ноды, и вызываем рекурсию для прохождения по левому и правому дерева и сбора счетчиков значений с их нод. Дальше с помощью функции max находим все максимальные значения счетчика и возвращаем их в списке.
Анализ сложности
Задано n как количество узлов в дереве,
Временная сложность: O(n)
В процессе dfs мы посещаем каждый узел один раз. В каждом узле мы выполняем работу O(1)), так как операции с хэш-картами стоят O(1).
Далее мы находим maxFreq, что предполагает итерацию по счетчику. В наихудшем случае, когда дерево имеет только уникальные значения, счетчик будет иметь размер nnn, и, следовательно, это будет стоить O(n).
Наконец, мы строим ans, что предполагает повторную итерацию над счетчиком. В целом, наша временная сложность составляет O(n).
Пространственная сложность: O(n)
При DFS рекурсия выполняется с использованием стека вызовов. Этот стек вызовов равен глубине дерева, что в худшем случае составляет O(n). Кроме того, как уже говорилось выше, если в дереве есть только уникальные значения, то счетчик будет иметь размер n. Таким образом, счетчик также использует O(n) пространства.
Грубый перевод разбора c LeetCode.
