DEV Community

faangmaster
faangmaster

Posted on

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

Ссылка на задачу на 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;
      }
    }
Enter fullscreen mode Exit fullscreen mode

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;
        }
    }
Enter fullscreen mode Exit fullscreen mode

Image of Timescale

🚀 pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applications—without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read full post →

Top comments (0)

AWS Security LIVE!

Tune in for AWS Security LIVE!

Join AWS Security LIVE! for expert insights and actionable tips to protect your organization and keep security teams prepared.

Learn More

Retry later