DFS: Задачи на деревья

Обход деревьев с помощью DFS. Диаметр, валидация BST, пути, сумма путей.

#1. Diameter of Binary Tree (LeetCode 543) 🟦 Medium

Ссылка: https://leetcode.com/problems/diameter-of-binary-tree/

Условие: Найдите диаметр бинарного дерева — максимальное расстояние между любыми двумя узлами.

Примеры:

Ввод: root = [1,2,3,4,5]
Вывод: 3
Объяснение: Путь [4,2,1,3] или [5,2,1,3]

Решение:

def diameterOfBinaryTree(root):
    diameter = [0]

    def height(node):
        if not node:
            return 0

        left_h = height(node.left)
        right_h = height(node.right)

        # Диаметр через этот узел
        diameter[0] = max(diameter[0], left_h + right_h)

        return 1 + max(left_h, right_h)

    height(root)
    return diameter[0]

Объяснение:

Диаметр через узел = высота левого + высота правого
Функция height возвращает высоту, обновляя диаметр
Используем список [0] для изменяемого счётчика

Сложность: O(n)

#2. Validate Binary Search Tree (LeetCode 98) 🟦 Medium

Ссылка: https://leetcode.com/problems/validate-binary-search-tree/

Условие: Проверьте, является ли дерево валидным BST.

Примеры:

Ввод: root = [2,1,3]
Вывод: true

Ввод: root = [5,1,4,null,null,3,6]
Вывод: false

Решение:

def isValidBST(root):
    def dfs(node, min_val, max_val):
        if not node:
            return True

        if not (min_val < node.val < max_val):
            return False

        return (dfs(node.left, min_val, node.val) and
                dfs(node.right, node.val, max_val))

    return dfs(root, float('-inf'), float('inf'))

Объяснение:

Передаём допустимый диапазон [min_val, max_val]
Для левого поддерева: max_val = node.val
Для правого поддерева: min_val = node.val

Сложность: O(n)

#3. Sum of All Path Numbers (LeetCode 129) 🟦 Medium

Ссылка: https://leetcode.com/problems/sum-root-to-leaf-numbers/

Условие: Дерево содержит цифры 0-9. Каждый путь от корня к листу — число. Найдите сумму всех чисел.

Примеры:

Ввод: root = [1,2,3]
Вывод: 25
Объяснение: 12 + 13 = 25

Решение:

def sumNumbers(root):
    def dfs(node, current_sum):
        if not node:
            return 0

        current_sum = current_sum * 10 + node.val

        # Лист
        if not node.left and not node.right:
            return current_sum

        return dfs(node.left, current_sum) + dfs(node.right, current_sum)

    return dfs(root, 0)

Объяснение:

current_sum = current_sum * 10 + node.val
Суммируем результаты левого и правого поддеревьев

Сложность: O(n)

#4. Binary Tree Paths (LeetCode 257) 🟩 Easy

Ссылка: https://leetcode.com/problems/binary-tree-paths/

Условие: Верните все пути от корня к листьям.

Примеры:

Ввод: root = [1,2,3,null,5]
Вывод: ["1->2->5", "1->3"]

Решение:

def binaryTreePaths(root):
    result = []

    def dfs(node, path):
        if not node:
            return

        path += str(node.val)

        # Лист
        if not node.left and not node.right:
            result.append(path)
            return

        path += '->'
        dfs(node.left, path)
        dfs(node.right, path)

    dfs(root, '')
    return result

Сложность: O(n × h)

#5. Шпаргалка

Задача	Ключевая идея
Diameter	height + update diameter
Validate BST	Передаём диапазон
Sum Paths	current_sum * 10 + val
Binary Paths	Строим строку пути

#6. ⚠️ Common Mistakes

#❌ Ошибка 1: Неправильный диапазон для BST

# ❌ Неправильно — только сравнение с детьми
if node.left.val < node.val < node.right.val:

# ✅ Правильно — диапазон для всего поддерева
dfs(node.left, min_val, node.val)
dfs(node.right, node.val, max_val)

#❌ Ошибка 2: Забыли базовый случай для листа

# ❌ Неправильно
def dfs(node, path):
    path += str(node.val)
    dfs(node.left, path)  # Может быть None!

# ✅ Правильно
if not node.left and not node.right:
    result.append(path)
    return

#7. Заключение

DFS: Задачи на деревья — обход деревьев с вычислением свойств.

Ключевые приёмы:

Diameter: высота + обновление диаметра
Validate BST: передача диапазона
Sum Paths: накопление числа через * 10

Задача

Ключевая идея

Diameter

height + update diameter

Validate BST

Передаём диапазон

Sum Paths

current_sum * 10 + val

Binary Paths

Строим строку пути

DFS: Деревья