Що робить level-order traversal (обхід дерева по рівнях)?

АлгоритмиJunior~2 хв читання

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

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 по рівнях (покроково)

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

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

Використання 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]] - обхід у ширину з чергою.

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

Для співбесіди

Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.