Binary Tree Zigzag Level Order Traversal

Problem

Given the root of a binary tree, return the zigzag level order traversal of its nodes' values. (i.e., from left to right, then right to left for the next level and alternate between).

Example 1:

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

Example 2:

Input: root = [1]
Output: [[1]]

Example 3:

Input: root = []
Output: []

Constraints:

The number of nodes in the tree is in the range [0, 2000].
-100 <= Node.val <= 100

Solution

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var zigzagLevelOrder = function(root) {
    const queue = root ? [root] : [];
    const res = [];
    let level = 0;

    while (queue.length) {
        const n = queue.length;
        const list = [];
        for (let i = 0; i < n; i++) {
            let index = level % 2 ? n - i - 1 : i;
            const node = queue.shift();
            list[index] = node.val;

            if (node.left) {
                queue.push(node.left);
            }
            if (node.right) {
                queue.push(node.right);
            }
        }
        level++;
        res.push(list);
    }
    return res;
};

We will implement a BFS solution. This solution is almost identical to Binary Tree Level Order Traversal. The only difference is that depending on the level we are on (ie. every other level), we sometimes need to have the node values in reverse order.

Problem​

Solution​

Problem

Solution