Обход дерева в ширину (BFS)

Обход дерева в ширину (BFS)

Описание

Breadth-First Search (BFS) — это алгоритм обхода графов и деревьев, который посещает узлы по уровням: сначала все узлы на уровне 1, затем на уровне 2, и так далее. Используется очередь (queue) для отслеживания узлов.

Решение 1: Классическое решение с использованием deque

from collections import deque

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

def bfs(root):
    """Обход дерева в ширину."""
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        node = queue.popleft()  # Извлекаем из начала
        result.append(node.value)
        
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    
    return result

# Пример использования
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

print(bfs(root))  # [1, 2, 3, 4, 5]

Временная сложность: O(n), где n — количество узлов. Пространственная сложность: O(w), где w — максимальная ширина дерева (на одном уровне).

Решение 2: С использованием обычного списка (медленнее)

def bfs(root):
    """BFS с использованием списка вместо deque."""
    if not root:
        return []
    
    result = []
    queue = [root]
    
    while queue:
        node = queue.pop(0)  # O(n) операция!
        result.append(node.value)
        
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    
    return result

⚠️ Примечание: pop(0) из списка имеет O(n) сложность! Используйте deque для O(1).

Решение 3: BFS с уровнями (возвращает двумерный список)

from collections import deque

def bfs_by_level(root):
    """BFS, возвращающий узлы по уровням."""
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level_size = len(queue)  # Количество узлов на текущем уровне
        current_level = []
        
        # Обрабатываем все узлы на текущем уровне
        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.value)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(current_level)
    
    return result

print(bfs_by_level(root))  # [[1], [2, 3], [4, 5]]

Решение 4: Рекурсивный BFS (менее интуитивный)

from collections import deque

def bfs_recursive(root):
    """Рекурсивная реализация BFS."""
    result = []
    
    def bfs_helper(queue):
        if not queue:
            return
        
        node = queue.popleft()
        result.append(node.value)
        
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
        
        bfs_helper(queue)
    
    if root:
        bfs_helper(deque([root]))
    
    return result

Решение 5: BFS для поиска (возвращает True/False)

from collections import deque

def contains_value(root, target):
    """Поиск значения в дереве с помощью BFS."""
    if not root:
        return False
    
    queue = deque([root])
    
    while queue:
        node = queue.popleft()
        
        if node.value == target:
            return True
        
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    
    return False

print(contains_value(root, 4))  # True
print(contains_value(root, 10))  # False

Решение 6: BFS для поиска кратчайшего пути

from collections import deque

def shortest_path(root, target):
    """Находит кратчайший путь до узла с целевым значением."""
    if not root:
        return None
    
    if root.value == target:
        return [root.value]
    
    queue = deque([(root, [root.value])])
    
    while queue:
        node, path = queue.popleft()
        
        if node.left:
            if node.left.value == target:
                return path + [node.left.value]
            queue.append((node.left, path + [node.left.value]))
        
        if node.right:
            if node.right.value == target:
                return path + [node.right.value]
            queue.append((node.right, path + [node.right.value]))
    
    return None

Сравнение BFS и DFS

Тестирование

def test_bfs():
    # Тест 1: Пустое дерево
    assert bfs(None) == []
    
    # Тест 2: Одиночный узел
    single = TreeNode(1)
    assert bfs(single) == [1]
    
    # Тест 3: Полное дерево
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(5)
    assert bfs(root) == [1, 2, 3, 4, 5]
    
    print("Все тесты пройдены!")

test_bfs()

Рекомендуемое решение для интервью

from collections import deque

def bfs(root):
    """BFS обход бинарного дерева.
    
    Args:
        root: корневой узел дерева
    
    Returns:
        Список значений узлов в порядке BFS
    
    Временная сложность: O(n)
    Пространственная сложность: O(w)
    """
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        node = queue.popleft()
        result.append(node.value)
        
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    
    return result

Ключевые моменты при объяснении:

• Используйте deque из collections для O(1) операций
• Объясните разницу между BFS и DFS
• Обсудите временную и пространственную сложность
• Покажите применение для поиска кратчайшего пути