Diameter, Validate BST, Sum Paths, Binary Tree Paths.
Обход деревьев с помощью DFS. Диаметр, валидация BST, пути, сумма путей.
Условие: Найдите диаметр бинарного дерева — максимальное расстояние между любыми двумя узлами.
Примеры:
Ввод: 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]Объяснение:
Сложность: O(n)
Условие: Проверьте, является ли дерево валидным 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'))Объяснение:
Сложность: O(n)
Условие: Дерево содержит цифры 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)Объяснение:
Сложность: O(n)
Условие: Верните все пути от корня к листьям.
Примеры:
Ввод: 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)
| Задача | Ключевая идея |
|---|---|
| Diameter | height + update diameter |
| Validate BST | Передаём диапазон |
| Sum Paths | current_sum * 10 + val |
| Binary Paths | Строим строку пути |
# ❌ Неправильно — только сравнение с детьми
if node.left.val < node.val < node.right.val:
# ✅ Правильно — диапазон для всего поддерева
dfs(node.left, min_val, node.val)
dfs(node.right, node.val, max_val)# ❌ Неправильно
def dfs(node, path):
path += str(node.val)
dfs(node.left, path) # Может быть None!
# ✅ Правильно
if not node.left and not node.right:
result.append(path)
returnDFS: Задачи на деревья — обход деревьев с вычислением свойств.
Ключевые приёмы:
Вопросы ещё не добавлены
Вопросы для этой подтемы ещё не добавлены.