Обход бинарного дерева по уровням

Источник задачи: https://leetcode.com/problems/binary-tree-level-order-traversal/

Дан корень root бинарного дерева. Вернуть обход дерева по уровням, то есть слева направа, уровень за уровнем.

Пример 1:

 

Дано: root = [3,9,20,null,null,15,7]
Результат: [[3],[9,20],[15,7]]

Пример 2:

Дано: root = [1]
Результат: [[1]]

Пример 3:

Дано: root = []
Результат: []

Ограничения:

• Число вершин дерева находятся в диапазоне [0, 2000].
• -1000 <= Node.val <= 1000 
  

 

Теория. Как можно обходить деревья

Есть 2 основные стратегии обхода дерева:

Depth First Search (DFS) - обход в глубину

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

Стратегия DFS дополнительно может быть разделена на предварительный порядок (preorder), порядок следования (inorder) и последующий порядок (postorder) в зависимости от относительного порядка между корневым узлом, левым узлом и правым узлом.

Breadth First Search (BFS) - обход в ширину

Мы сканируем дерево уровень за уровнем (этаж за этажом), снизу вверх. Вершины более верхнего уровня будут посещены раньше, чем вершины с нижних уровней.

Схемы разных обходов:

Имплементация

/**

 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
// результат будет списком списков (список этажей)
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (root == null) return result; //  если дан нулевой элемент, то и возвращать нечего

// для обхода по этажам дерева нужна очередь
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.add(root); //  заносим корень в очередь - это первый этаж дерева
        while (!q.isEmpty()) {
// в начале итерации содержимое очереди - это содержимое этажа
// запоминаем, сколько элементов на этаже
            int currentLevelSize = q.size();
// для текущего этажа создаем отдельный список
            List<Integer> level = new ArrayList<Integer>();
// рассматриваем каждый элемент этажа
            for (int i = 0; i < currentLevelSize; i++) {
                TreeNode node = q.remove(); // убираем его из очереди
                level.add(node.val);  // добавлем значение элемента в список, который нужно вернуть
// заносим в очередь его левый/правый подэлемет, если они существуют
                if (node.left!=null) q.add(node.left);
                if (node.right!=null) q.add(node.right);
            }
            result.add(level); //  добавляем сформированный список этажа в список всех этажей
        }
        return result;
    }
}