Запропонувати правку

Покращити цю статтю

Допрацюйте відповідь до «Що робить level-order traversal (обхід дерева по рівнях)?». Ваші зміни проходять модерацію перед публікацією.

Потрібне підтвердження

Контент

Що ви змінюєте

Заголовок (UA)

Коротка відповідь (UA)

Показується над повною відповіддю для швидкого нагадування.

Відповідь (UA)

## Коротка відповідь

Level-order traversal (обхід дерева по рівнях) - це обхід вузлів дерева по шарах від кореня до листя зліва направо з використанням черги (BFS). Він відвідує спочатку всі вузли на глибині 0, потім на глибині 1, потім на глибині 2 і так далі.

## Детальне пояснення

- Що робить: відвідує вузли в порядку незростаючої відстані по ребрах від кореня, групуючи їх за рівнями глибини.
- Як працює: використовує чергу. Беремо корінь, поміщаємо в чергу; поки черга не порожня - дістаємо поточний рівень (кількість елементів = поточний розмір черги), послідовно додаємо в чергу всіх дітей кожного вузла.
- Результат: можна отримати або пласку послідовність, або список рівнів (масив масивів).
- Складність: час O(n), де n - кількість вузлів; пам'ять O(w), де w - максимальна ширина дерева (у гіршому O(n)).
- Відмінність від DFS: DFS заглиблюється по гілці (pre/in/postorder), а level-order - це BFS упоперек рівнів.
- Застосування: друк/серіалізація дерев, задачі на «правий/лівий вид», з'єднання next-покажчиків між сусідами, суми за рівнями, пошук найкоротшого шляху в неважених структурах тощо.

### Приклад дерева і очікуваний результат

```
Дерево:

1
   / \
  2   3
 / \   \
4   5   6

Рівні: [[1], [2, 3], [4, 5, 6]]
Пласко: [1, 2, 3, 4, 5, 6]
```

### Ітеративна реалізація (JavaScript, бінарне дерево)

```
// Визначення вузла для контексту:
// function TreeNode(val, left=null, right=null) { this.val = val; this.left = left; this.right = right; }

function levelOrder(root) {
  if (!root) return [];
  const res = [];
  const q = [root]; // черга
  let head = 0;     // покажчик на "голову" черги (уникаємо O(n) shift)

while (head < q.length) {
    const size = q.length - head; // кількість вузлів на поточному рівні
    const level = [];

for (let i = 0; i < size; i++) {
      const node = q[head++];
      level.push(node.val);
      if (node.left) q.push(node.left);
      if (node.right) q.push(node.right);
    }

res.push(level);
  }
  return res;
}

// Приклад:
// const root = new TreeNode(1,
//   new TreeNode(2, new TreeNode(4), new TreeNode(5)),
//   new TreeNode(3, null, new TreeNode(6))
// );
// console.log(levelOrder(root)); // [[1], [2, 3], [4, 5, 6]]
```

### N-арне дерево (JavaScript)

```
// Вузол N-арного дерева: { val, children: Node[] }
function levelOrderN(root) {
  if (!root) return [];
  const res = [];
  const q = [root];
  let head = 0;

while (head < q.length) {
    const size = q.length - head;
    const level = [];

for (let i = 0; i < size; i++) {
      const node = q[head++];
      level.push(node.val);
      if (node.children) {
        for (const child of node.children) {
          if (child) q.push(child);
        }
      }
    }

res.push(level);
  }
  return res;
}
```

### Варіант: плаский обхід без групування рівнів

```
function bfsFlat(root) {
  if (!root) return [];
  const out = [];
  const q = [root];
  let head = 0;
  while (head < q.length) {
    const node = q[head++];
    out.push(node.val);
    if (node.left) q.push(node.left);
    if (node.right) q.push(node.right);
  }
  return out;
}
```

### Шаблон BFS по рівнях (покроково)

1. Ініціалізувати чергу коренем; результат - порожній.
2. Поки черга не порожня: зафіксувати size = поточний розмір рівня.
3. Повторити size разів: витягти вузол, записати значення, додати всіх його дітей у чергу.
4. Зберегти зібраний масив як один рівень результату.

### Часті помилки і підводні камені

- Використання Array.shift() у JS - призводить до O(n) на вилучення; краще використовувати індекс голови.
- Забувають розділяти рівні: потрібна або змінна size, або маркер рівня (null-роздільник).
- Не обробляють порожній корінь: одразу повертайте порожній результат.
- Плутають з DFS і очікують інший порядок обходу.

### Пов'язані варіанти задач

- Друк зигзагом (zigzag level order): на парних рівнях реверсувати порядок.
- Bottom-up order: зібрати рівні і в кінці розвернути масив рівнів.
- Right/Left side view: брати останній/перший елемент кожного рівня.
- Суми/середні за рівнем: накопичувати агрегати під час проходження.
- З'єднати сусідні next-покажчики в повному бінарному дереві.
- Серіалізація/десеріалізація дерев (наприклад, через список рівнів).

### Порівняння з preorder/inorder/postorder

- Preorder (корінь-ліво-право): 1,2,4,5,3,6 - обхід у глибину, стек.
- Inorder (ліво-корінь-право): 4,2,5,1,3,6 - застосовується до бінарних дерев.
- Postorder (ліво-право-корінь): 4,5,2,6,3,1 - обхід у глибину.
- Level-order: 1,2,3,4,5,6 або за рівнями [[1],[2,3],[4,5,6]] - обхід у ширину з чергою.

Markdown · перетягуйте зображення · ⌘B / ⌘I шорткати671 слів

Для рев’юера

Примітка для модератора (необов’язково)

Бачить лише модератор. Прискорює рев’ю.