102. Обход порядка уровней двоичного дерева 🚀

Решение разработано в:

Вопрос

В этой статье мы рассмотрим вопрос Leetcode ‘102. Обратный путь к порядку уровня двоичного дерева». Этот вопрос оценивается как средний.

Вопрос:

Задав корень двоичного дерева, верните порядок уровня обхода значений его узлов. (т.е. от левого к правому, уровень за уровнем).

Пример:

    3
   / 
  9  20
    /  
   15   7

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

Объяснение вопроса

Этот вопрос оценивается как средний. Что, на мой взгляд, вполне справедливо для этого вопроса о двоичном дереве.

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

Это означает, что если у вас 10 слоев двоичного дерева, то у вас должно быть 10 массивов. Которые представляют 10 слоев двоичного дерева.

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

Рекомендуемые знания

1. Бинарное дерево
2. Поиск по глубине
3. Порядковый обход
4. Обход по порядку уровней
5. Очередь

Что мы знаем?

1. Нам было дано двоичное дерево.
2. Наше дерево имеет несколько слоев.
3. Эти слои нужно обойти и сохранить.
4. Каждый слой должен иметь свой собственный ряд.
5. Мы вернем коллекцию этих массивов. Это будет массив рядов.

Как мы собираемся это сделать:

Мы собираемся использовать вариант итеративного алгоритма обхода порядка слоев (In-order). Это означает, что мы будем посещать каждый узел в формате «слой за слоем». Для этого вопроса вы уже должны знать, как это делается.

От обычного обхода по порядку уровней мы будем отличаться тем, что будем использовать цикл for для итерации по каждому слою. Каждый слой представлен тем, что находится в очереди. Ключевым отличием является то, что мы будем посещать ТОЛЬКО те узлы, которые находятся на этом уровне, но, несмотря на это, мы будем знать, какие узлы будут следующими. Это немного сбивает с толку.

Итак, для каждого слоя мы добавим значение данного узла в массив row, а затем добавим дочерние узлы в очередь. ‘Но, конечно, в итоге мы просто пройдемся по всему дереву таким образом, а не слой за слоем!!!’. Да, так бы и было, если бы мы не отслеживали длину очереди, прежде чем начать добавлять в нее новые элементы, но мы ее отслеживаем. Поэтому мы всегда знаем длину слоя.

1. Во-первых, мы объявим нашу queue для обхода дерева по порядку уровней. Мы также объявим наш level_order_array, который будет нашим возвращаемым значением. Здесь мы будем выталкивать каждую строку в него.
2. Мы объявим наш массив row. Который, конечно же, будет представителем каждого слоя бинарных деревьев.
3. Итак, мы будем хранить длину очереди. Которая будет равна длине текущего слоя. Для каждого узла в этом слое мы добавим его в массив row. Одновременно добавляя их дочерние узлы в очередь. Но поскольку нам нужны только узлы этого слоя, мы будем выполнять цикл for только для начальной длины данной queue.

Нотация Big O:

• Временная сложность: O(n)| Где n — количество узлов в нашем двоичном дереве | Поскольку мы собираемся обойти все узлы в дереве.
• Сложность пространства: O(q)| Где q — длина очереди двоичного дерева.

Результаты Leetcode:

См. ссылку на представление:

• Время выполнения: 77 мс, быстрее, чем 64,38% онлайн-заявок JavaScript для обхода порядка уровней двоичного дерева
• Использование памяти: 44,5 МБ, меньше, чем в 35,08% случаев использования JavaScript для обхода порядка уровней двоичного дерева.

Решение

var levelOrder = function (root) {

    // Empty tree
    // Return a empty array
    if (!root) {
        return [];
    }

    // Level Order Array, will store each row of the tree
    let level_order_array = [];
    let queue = [root];

    // We're going to be using a iterative approach to this.
    // With use of a queue we're able to achieve level order traversal.
    while (queue.length) {

        // We're going to create a new row each time
        // we encounter a new level.
        let row = [];

        // This is the important part.
        // We keep track of the initial length of the queue
        // We do this because, as we iterate through the queue we don't
        // want to accidentally pick up items from another.
        let queue_len = queue.length;

        // So for every item currently in the queue
        // we're going to add it to the row
        // All the while adding new items to the queue,
        // but because we kept memory of the input length
        // we will only ever pick up the items for that row.
        for (let i = 0; i < queue_len; i++) {

            // Get the node, by popping it off the queue
            let node = queue.pop();

            // Add the node to the row (This row is the given layer)
            row.push(node.val);

            // Just like in a normal level order traversal,
            // when we see a child node, we add it to the queue,
            // but because we kept memory of the input length
            // we won't technically run these children items
            // until we reach their row.
            node.left ? queue.unshift(node.left) : null;
            node.right ? queue.unshift(node.right) : null;
        }

        // So we have gone through the entire queue.
        // Push that row to the level order array.
        level_order_array.push(row);
    }

    return level_order_array;
};