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

Вопрос

В этой статье мы рассмотрим вопрос Leetcode ‘103. Обход зигзагообразного порядка двоичного дерева».

Вопрос:

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

Пример:

Input: root = [1,null,0,0,1]
Output: [1,null,0,null,1]
Explanation: 
Only the red nodes satisfy the property "every subtree not containing a 1".
The diagram on the right represents the answer.

Пояснение к вопросу

Этот вопрос оценивается как средний. Что, на мой взгляд, вполне соответствует действительности. Во многих отношениях этот вопрос является преемником вопроса ‘102. Обход порядкового уровня двоичного дерева». Если вы знакомы с тем вопросом, вы сможете понять этот вопрос.

То, что нас просят сделать, аналогично вопросу 102. Обход порядка уровней двоичного дерева. Но с некоторым отличием — нам нужно сделать это зигзагообразно. Это означает, что нам нужно чередовать левую и правую стороны. Обычно мы просто идем слева -> справа. Как если бы мы читали книгу. Хотя в данном вопросе нам нужно идти влево -> направо, а затем направо -> налево. Буквальный зигзаг.

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

Поэтому всякий раз, когда мы добавляем значение к row, мы также спрашиваем? Добавить ли мне это значение в начало или в конец массива? Вот и все. 😁

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

1. Двоичное дерево
2. Поиск по глубине
3. Обход по порядку уровней
4. 102. Обход порядка уровней двоичного дерева (Умеет делать это с легкостью)
5. Стек

Что мы знаем?

1. У нас есть двоичное дерево (в большинстве случаев оно может быть пустым).
2. Нам нужно хранить все строки двоичного дерева в массиве, который будет представлять обход порядка уровней
3. Нам нужно выполнить обход двоичного дерева в порядке уровней, но зигзагообразно.

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

Мы будем реализовывать решение, аналогичное 102. Обращение к порядку уровней двоичного дерева. Это заключается в использовании queue для хранения узлов row. При этом мы всегда очищаем все узлы в queue, переходя к следующей строке.

Ключевое отличие здесь в том, что у нас установлен флаг zigzag для чередования значений true и false. True означает, что нам нужно идти right -> left, а false означает, что нам нужно идти left -> right. Мы делаем это с помощью методов unshift и push.

Всякий раз, когда нам нужно добавить узел в row, мы спрашиваем? Добавить ли мне это значение в начало или в конец массива? Поэтому, если флаг zigzag равен true, мы добавляем узел в начало массива с помощью операции unshift, как если бы это была queue. Если флаг zigzag равен false, мы добавляем узел в конец массива, как если бы это был stack.

Таким образом, в итоге мы получаем не зигзагообразный обход, а нечто, имитирующее его. Технически говоря, мы обходим бинарное дерево в порядке уровней. Но то, как мы добавляем узлы в строку — это зигзаг.

Нотация Big O:

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

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

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

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

• Время выполнения: 69 мс, быстрее, чем 76,64% представленных в сети JavaScript для обхода зигзагообразного порядка уровней двоичного дерева.
• Использование памяти: 43,5 МБ, меньше, чем в 95,97% случаев использования JavaScript для обхода двоичного дерева с зигзагообразным порядком уровней.

Решение

var zigzagLevelOrder = function (root) {

    // What we do here is perform the normal
    // level order traversal in rows.
    // But we instead use a stack / queue depending
    // on if we're to zig zag or not.

    // Base case, we have no root.
    if (!root) {
        return [];
    }

    // So we're going to need a queue for the level order traversal.
    // We're also going to need a level_order array to store all the rows 
    // of the binary tree
    // as well as a flag to invert the order of the rows or not
    // (zig zag). Meaning, if we're going to zig zag, we'll get the first node in the queue
    // if we're not zig zag, we'll get the last node in the queue. (Unshift / pop)
    let queue       = [root];
    let level_order = [];
    let zigzag      = true;

    // So we perform a normal iterative level order traversal.
    while (queue.length) {

        // This will be our row, it will store all the nodes for the row in the tree
        let row       = [];
        let queue_len = queue.length;

        // So we're always going to invert the order of the rows.
        // We do this to create our zig zag effect.
        // Back, forward, back, forward, etc.
        zigzag = !zigzag;

        // We're going to get everything in the queue.
        // at this particular moment and nothing more.
        for (let counter = 0; counter < queue_len; counter++) {

            // Grab the current node by removing it off the end of the queue
            let node = queue.pop();

            // So, if the invert flag is set, we're going to push the current node
            // to the START of the row. Which means, we will produce a zig zag effect.
            // Without having to change the order in which we visit our nodes.
            // If the invert flag is not set, we're going to push the current node
            // to the end of the row stack like we normally would in level order traversal.
            if (zigzag) {
                row.unshift(node.val);
            } else {
                row.push(node.val);
            }

            // Add to the queue. 
            node.left  ? queue.unshift(node.left) : null;
            node.right ? queue.unshift(node.right): null;
        }

        // Push to the level_order array.
        level_order.push(row);
    }

    // Return the level_order array.
    return level_order;
};