Минимальная глубина бинарного дерева

Question

## Условие

Найдите минимальную глубину бинарного дерева.

Минимальная глубина — это кратчайший путь от корня до ближайшего листа.

## Пример

```
    3
   / \
  9  20
    /  \
   15   7
```

Ответ: 2 (путь 3 → 9)

claude-haiku-4.5 · Accepted Answer

## Минимальная глубина бинарного дерева

Это популярная задача на обход деревьев. Важно понять разницу между минимальной и максимальной глубиной, а также оптимизировать обход.

### 1. Определение минимальной глубины

**Минимальная глубина** = длина пути от корня до ближайшего листа.

**Лист** = узел без потомков (нет левого и правого детей).

```
Примеры:

3           3           3
   / \         /           / \
  9  20      9            9  20
    /  \                     /  \
   15   7                   15   7

Ответ: 2     Ответ: 2    Ответ: 2
Лист: 9      Лист: 9     Листья: 15, 7 → мин=2
```

### 2. Определение структуры дерева

```python
from typing import Optional

class TreeNode:
    def __init__(self, val: int = 0, left: Optional['TreeNode'] = None, 
                 right: Optional['TreeNode'] = None):
        self.val = val
        self.left = left
        self.right = right
```

### 3. Наивное решение — DFS (рекурсия)

```python
def minDepth_naive(root: Optional[TreeNode]) -> int:
    """Найти минимальную глубину рекурсивно (неоптимально)."""
    
    # Базовый случай: пустое дерево
    if not root:
        return 0
    
    # Если это лист (нет детей)
    if not root.left and not root.right:
        return 1
    
    # Рекурсивно ищем минимум в обоих поддеревьях
    left_depth = minDepth_naive(root.left) if root.left else float('inf')
    right_depth = minDepth_naive(root.right) if root.right else float('inf')
    
    return 1 + min(left_depth, right_depth)

# Проблема: посещаем ВСЕ узлы, даже если найдём лист раньше
```

**Анализ:**
- **Время:** O(n) в худшем случае (посещаем все узлы)
- **Память:** O(h) где h — высота дерева (стек рекурсии)

### 4. Оптимальное решение — BFS (очередь)

**BFS найдёт первый лист быстрее, чем DFS!**

```python
from collections import deque

def minDepth_optimal(root: Optional[TreeNode]) -> int:
    """Найти минимальную глубину через BFS (оптимально)."""
    
    if not root:
        return 0
    
    # Очередь содержит (узел, глубина)
    queue = deque([(root, 1)])
    
    while queue:
        node, depth = queue.popleft()
        
        # Если нашли лист — возвращаем сразу!
        if not node.left and not node.right:
            return depth
        
        # Добавляем потомков в очередь
        if node.left:
            queue.append((node.left, depth + 1))
        if node.right:
            queue.append((node.right, depth + 1))
    
    return 0

# Оптимизация: BFS останавливается на первом листе!
```

**Анализ:**
- **Время:** O(n) в худшем случае, но часто O(log n) — O(n/2) на практике
- **Память:** O(w) где w — максимальная ширина дерева
- **Преимущество:** Ранний выход при нахождении листа

### 5. Визуализация BFS vs DFS

```
Дерево:
        3
       / \
      9  20
        /  \
       15   7

BFS (очередь):
Шаг 1: Посещаем 3 (глубина=1) → это не лист, добавляем детей
Шаг 2: Посещаем 9 (глубина=2) → это ЛИСТ! Ответ: 2

Визит узлов: 3, 9 (всего 2 узла)

DFS (стек):
Шаг 1: Посещаем 3 → спускаемся в левое поддерево
Шаг 2: Посещаем 9 → это лист, возвращаемся
Шаг 3: Посещаем левое поддерево 20
Шаг 4: Посещаем 15 → это лист
Шаг 5: Посещаем 7 → это лист

Визит узлов: 3, 9, 20, 15, 7 (всего 5 узлов)

BFS эффективнее на 60%!
```

### 6. Правильное решение DFS

Если используем DFS, нужно правильно обработать случаи:

```python
def minDepth_dfs(root: Optional[TreeNode]) -> int:
    """DFS решение с правильной логикой."""
    
    if not root:
        return 0
    
    # Если узел листа:
    if not root.left and not root.right:
        return 1
    
    # ВАЖНО: если один из детей отсутствует,
    # это НЕ листья! Нельзя просто возвращать float('inf')
    left_depth = minDepth_dfs(root.left) if root.left else float('inf')
    right_depth = minDepth_dfs(root.right) if root.right else float('inf')
    
    return 1 + min(left_depth, right_depth)

# Альтернатива (более ясная):
def minDepth_dfs_clear(root: Optional[TreeNode]) -> int:
    """DFS с явной обработкой случаев."""
    
    if not root:
        return 0
    
    # Лист: оба потомка None
    if not root.left and not root.right:
        return 1
    
    # Внутренний узел: минимум из существующих поддеревьев
    min_child_depth = float('inf')
    
    if root.left:
        min_child_depth = min(min_child_depth, minDepth_dfs_clear(root.left))
    
    if root.right:
        min_child_depth = min(min_child_depth, minDepth_dfs_clear(root.right))
    
    return 1 + min_child_depth
```

### 7. Полный пример с тестами

```python
from typing import Optional
from collections import deque
import unittest

class TreeNode:
    def __init__(self, val: int = 0, left: Optional['TreeNode'] = None,
                 right: Optional['TreeNode'] = None):
        self.val = val
        self.left = left
        self.right = right

def minDepth(root: Optional[TreeNode]) -> int:
    """Оптимальное решение через BFS."""
    if not root:
        return 0
    
    queue = deque([(root, 1)])
    
    while queue:
        node, depth = queue.popleft()
        
        # Нашли лист — возвращаем сразу
        if not node.left and not node.right:
            return depth
        
        # Добавляем потомков
        if node.left:
            queue.append((node.left, depth + 1))
        if node.right:
            queue.append((node.right, depth + 1))
    
    return 0

class TestMinDepth(unittest.TestCase):
    
    def setUp(self):
        """Создаём тестовые деревья."""
        # Дерево 1:
        #     3
        #    / \
        #   9  20
        #     /  \
        #    15   7
        self.tree1 = TreeNode(3)
        self.tree1.left = TreeNode(9)
        self.tree1.right = TreeNode(20)
        self.tree1.right.left = TreeNode(15)
        self.tree1.right.right = TreeNode(7)
        
        # Дерево 2: только корень
        self.tree2 = TreeNode(1)
        
        # Дерево 3: пустое
        self.tree3 = None
        
        # Дерево 4: скошенное (только левые дети)
        #     1
        #    /
        #   2
        #  /
        # 3
        self.tree4 = TreeNode(1)
        self.tree4.left = TreeNode(2)
        self.tree4.left.left = TreeNode(3)
    
    def test_example_case(self):
        """Стандартный пример из задачи."""
        self.assertEqual(minDepth(self.tree1), 2)
    
    def test_single_node(self):
        """Дерево с одним узлом (листом)."""
        self.assertEqual(minDepth(self.tree2), 1)
    
    def test_empty_tree(self):
        """Пустое дерево."""
        self.assertEqual(minDepth(self.tree3), 0)
    
    def test_skewed_tree(self):
        """Скошенное дерево только с левыми детьми."""
        self.assertEqual(minDepth(self.tree4), 3)
    
    def test_complete_tree(self):
        """Полное сбалансированное дерево."""
        #       1
        #      / \
        #     2   3
        #    / \
        #   4   5
        tree = TreeNode(1)
        tree.left = TreeNode(2)
        tree.right = TreeNode(3)
        tree.left.left = TreeNode(4)
        tree.left.right = TreeNode(5)
        
        # Листья на уровне 3: 4, 5, 3
        # Минимальная глубина = 2 (путь 1→3)
        self.assertEqual(minDepth(tree), 2)
    
    def test_right_skewed_tree(self):
        """Скошенное дерево только с правыми детьми."""
        #     1
        #      \
        #       2
        #        \
        #         3
        tree = TreeNode(1)
        tree.right = TreeNode(2)
        tree.right.right = TreeNode(3)
        
        self.assertEqual(minDepth(tree), 3)

if __name__ == '__main__':
    unittest.main()
```

### 8. Сравнение подходов

| Подход | Времени | Памяти | Про | Минусы |
|--------|---------|--------|------|--------|
| BFS | O(n), но часто O(min_depth * log n) | O(w) | Ранний выход | Немного сложнее |
| DFS наивный | O(n) | O(h) | Простой | Посещает все узлы |
| DFS правильный | O(n) | O(h) | Простой | Посещает все узлы |

### 9. Сложные граничные случаи

```python
def handle_edge_cases():
    # Дерево, где корень имеет только одного ребёнка
    #     1
    #    /
    #   2
    tree = TreeNode(1)
    tree.left = TreeNode(2)
    # Минимальная глубина НЕ 1! (1 не лист)
    # Ответ: 2
    
    # Дерево с чередующимися детьми
    #       1
    #      / \
    #     2   3
    #    /     \
    #   4       5
    tree = TreeNode(1)
    tree.left = TreeNode(2)
    tree.right = TreeNode(3)
    tree.left.left = TreeNode(4)
    tree.right.right = TreeNode(5)
    # Листья: 4 (глубина 3), 5 (глубина 3)
    # Ответ: 3
```

### 10. Оптимизация памяти

```python
def minDepth_memory_optimized(root: Optional[TreeNode]) -> int:
    """Двусторонний BFS для экономии памяти."""
    if not root:
        return 0
    
    # Используем две очереди для двусторонней очереди
    from collections import deque
    
    if not root.left and not root.right:
        return 1
    
    queue = deque([(root, 1)])
    
    while queue:
        node, depth = queue.popleft()
        
        if not node.left and not node.right:
            return depth
        
        # Добавляем только существующих потомков
        if node.left:
            queue.append((node.left, depth + 1))
        if node.right:
            queue.append((node.right, depth + 1))
    
    return 0
```

### Вывод

**Для минимальной глубины бинарного дерева:**

1. **BFS оптимален** — находит первый лист быстро
2. **DFS нужно писать правильно** — обработать случаи с одним потомком
3. **Главная ошибка** — путать листья с узлами, имеющими одного потомка
4. **Граничные случаи** — пустое дерево, один узел, скошенные деревья

Выбирайте BFS для лучшей средней производительности!

Подход	Времени	Памяти	Про	Минусы
BFS	O(n), но часто O(min_depth * log n)	O(w)	Ранний выход	Немного сложнее
DFS наивный	O(n)	O(h)	Простой	Посещает все узлы
DFS правильный	O(n)	O(h)	Простой	Посещает все узлы

Минимальная глубина бинарного дерева

Условие

Пример

Комментарии (1)

Минимальная глубина бинарного дерева

1. Определение минимальной глубины

2. Определение структуры дерева

3. Наивное решение — DFS (рекурсия)

4. Оптимальное решение — BFS (очередь)

5. Визуализация BFS vs DFS

6. Правильное решение DFS

7. Полный пример с тестами

8. Сравнение подходов

9. Сложные граничные случаи

10. Оптимизация памяти

Вывод