Условие

Дано бинарное дерево поиска (BST). Необходимо найти все значения (моды), которые встречаются в дереве наиболее часто. Возвратить эти значения в виде массива.

Решение должно работать за O(n) времени и O(h) памяти, где n — количество узлов в дереве, а h — его высота.

Примеры

Input: root = [1,null,2,2] Output: [2]

Input: root = [0] Output: [0]

Решение

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
 fun findMode(root: TreeNode?): IntArray {
    var currentVal: Int? = null  // Хранит текущее значение, которое мы обрабатываем
    var currentCount = 0         // Счетчик для текущего значения
    var maxCount = 0             // Максимальная частота, найденная на данный момент
    val modes = mutableListOf<Int>()  // Список для хранения значений с максимальной частотой

    // Функция для обработки текущего значения и обновления счетчиков
    fun handleValue(value: Int) {
        // Если значение изменилось, сбрасываем счетчик для нового значения
        if (value != currentVal) {
            currentVal = value
            currentCount = 0
        }
        currentCount++  // Увеличиваем счетчик для текущего значения

        // Если текущая частота больше, обновляем максимальную частоту и сбрасываем список мод
        if (currentCount > maxCount) {
            maxCount = currentCount
            modes.clear()
            modes.add(value)  // Добавляем текущее значение как новое значение с максимальной частотой
        } else if (currentCount == maxCount) {
            // Если текущая частота равна максимальной, добавляем значение в список мод
            modes.add(value)
        }
    }

    // Функция для обхода дерева в порядке "in-order" (лево-корень-право)
    // Обход "in-order" подходит, так как в BST он дает отсортированный порядок значений
    fun inOrder(node: TreeNode?) {
        if (node == null) return  // Если узел пустой, возвращаемся

        inOrder(node.left)  // Рекурсивный вызов для левого поддерева
        handleValue(node.`val`)  // Обрабатываем текущее значение узла
        inOrder(node.right)  // Рекурсивный вызов для правого поддерева
    }

    // Запускаем обход дерева
    inOrder(root)

    // Преобразуем список мод в массив и возвращаем
    return modes.toIntArray()
}

Временная сложность

O(n), где n — количество узлов в дереве, так как мы проходим по каждому узлу один раз.

Пространственная сложность

O(h), где h — высота дерева, что соответствует глубине рекурсивного вызова на стеке для сбалансированного дерева.