Ссылка на задачу на leetcode: https://leetcode.com/problems/binary-tree-level-order-traversal/description/
Условие. Дано двоичное дерево. Нужно обойти его по слоям/уровням. Каждый уровень обходить слева направо. Результат вернуть в виде списка списков. Каждый вложенный список это элементы одного уровня.
Например:
Для такого дерева
Ответ: [[1], [2, 3], [3, 4, 5], [6]]
Решение. Для решения будем использовать поиск в ширину. Я описал алгоритм поиска в ширину тут: BFS.
Небольшая справка по деревьям.
Граф — это множество вершин и связей между ними.
Дерево — это связный граф, не содержащий циклов. Это древовидная структура, в которой есть корень, которой содержит ноль входящих ребер, а остальные вершины имеют ровно одно входящее ребро.
Двоичное дерево — дерево, в котором каждая вершина имеет не более двух дочерних вершин.
Класс вершины двоичного дерева можно описать на Java следующим образом:
class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val, TreeNode left, TreeNode right) {
this.val= val;
this.left = left;
this.right = right;
}
}
left и right — это левый и правый ребенок вершины. Для простоты, на собеседованиях можно не объявлять поля private и не использовать геттеры для получения доступа к полям. Это позволит обращаться к полям как node.left, node.right.
Вернемся к задаче.
Как я уже сказал, мы будем использовать BFS. Для случая дерева его можно упростить. Нам не нужно использовать visited. Т.к. мы будем идти от родителей к детям. Вечного цикла у нас не возникнет.
Чтобы понять когда у нас начался и закончился уровень, который мы обходим, нам нужно хранить в очереди номер уровня или элементы каждого уровня складывать в отдельную очередь.
Рассмотрим второй вариант, с отдельной очередью для каждого уровня. Поместим корень дерева в очередь. Создадим еще одну очередь для следующего уровня. Будем итерироваться по первой очереди, пока она не закончится, но помещать детей не в ту же самую очередь, а во вторую. Как только первая очередь закончится — заменим ее второй и повторим весь процесс.
Решение на Java:
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
if (root != null)
queue.add(root);
while (!queue.isEmpty()) {
//Вторая очередь для следующего уровня
Queue<TreeNode> newQueue = new LinkedList<>();
//Тут будем хранить элементы одного уровня
List<Integer> values = new ArrayList<>();
//Цикл по первой очереди, но детей помещаем во вторую очередь
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
values.add(node.val);
if (node.left != null)
newQueue.add(node.left);
if (node.right != null)
newQueue.add(node.right);
}
result.add(values);
//Подменяем первую очередь второй
queue = newQueue;
}
return result;
}
}
Top comments (0)