Условие задачи

Дано бинарное дерево с корнем root.

• Узел X считается "хорошим", если в пути от корня до узла X нет узлов со значением больше, чем у узла X.
• Необходимо вернуть количество "хороших" узлов в данном бинарном дереве.

Примеры

Пример 1:

Входные данные: root = [3,1,4,3,null,1,5]

Результат: 3

Объяснение: В данном примере "хорошими" узлами являются следующие узлы: 3, 1 и 5.

Решение

1. Создадим переменную count и инициализируем ее нулем.
2. Создадим функцию dfs(node, max_val), которая будет рекурсивно обходить дерево. Функция принимает два аргумента: node - текущий узел, max_val - максимальное значение узла на пути до текущего узла.
3. Если значение узла node больше или равно max_val, то узел node является "хорошим", увеличиваем count на единицу.
4. Если у узла node есть левый потомок, то вызываем dfs для левого потомка. Максимальное значение на пути до левого потомка - это максимум из max_val и значения узла node.
5. Аналогично, если у узла node есть правый потомок, то вызываем dfs для правого потомка. Максимальное значение на пути до правого потомка - это максимум из max_val и значения узла node.
6. Вызываем dfs для корневого узла root и возвращаем count.

Объяснение на примере

Для примера 1, дерево имеет следующий вид:

      3
     / \\\\
    1   4
   /   / \\\\
  3   1   5