1448. Count Good Nodes in Binary Tree

Обновлено: 2023-09-05
2 мин

LeetCode задача 1448

Задача

Дано бинарное дерево. Задача подсчитать количество “хороших” узлов. Узел считается “хорошим”, если на пути от корня дерева до этого узла (включительно) не встречается узлов с большим значением.

Подсказки

“Хороший” узел в дереве — это узел, для которого все узлы на пути от корня до этого узла имеют значение не больше, чем значение этого узла.

Использовать метод обхода в глубину (DFS) для решения этой задачи.

Подход

Идея решения задачи заключается в рекурсивном обходе дерева с сохранением максимального значения на пути от корня к текущему узлу. На каждом этапе, когда мы доходим до нового узла, мы сравниваем его значение с максимальным значением на пути. Если значение узла не меньше максимального, значит, это “хороший” узел.

Этот метод обеспечивает простой и понятный способ решения задачи, хотя и может быть не самым оптимальным по времени и памяти.

  1. Обход в глубину (DFS): Используйте рекурсивный метод для обхода дерева.
  2. Текущий максимум: На каждом шаге рекурсии передавайте текущее максимальное значение на пути от корня.
  3. Сравнение узлов: Сравните значение текущего узла с текущим максимумом. Если значение узла больше или равно, увеличьте счетчик “хороших” узлов.

Алгоритм

  1. Рекурсивно обходить дерево, начиная с корня.

  2. В процессе обхода обновлять максимальное значение на пути и считать “хорошие” узлы.

  3. Инициализируйте счетчик “хороших” узлов как 0.

  4. Запустите рекурсивный DFS, начиная с корня дерева и передавая значение корня как текущий максимум.

  5. В рекурсивной функции сравните значение текущего узла с переданным максимумом.

  6. Обновите текущий максимум, если значение текущего узла больше.

  7. Повторите шаги 2-4 для всех дочерних узлов.

Решение

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def goodNodes(root: TreeNode) -> int:
    def dfs(node, cur_max):
        if not node:
            return 0
        
        count = 0
        if node.val >= cur_max:
            count += 1
            cur_max = node.val
        
        count += dfs(node.left, cur_max)
        count += dfs(node.right, cur_max)
        
        return count
    
    return dfs(root, root.val)