1448. Count Good Nodes in Binary Tree

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)