103. Binary Tree Zigzag Level Order Traversal Medium

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: []

Approach

Input: The root node of a binary tree root.

Output: Return the values in a zigzag level order traversal.

This problem belongs to Binary Tree Traversal problems, typical Breadth-First Search (BFS), also known as level order traversal.

• We use a Queue to traverse the nodes level by level in a "left to right, top to bottom" order:
• Iteratively take all nodes of the current level out of the queue
• Access these nodes one by one, recording their values
• Add their left and right child nodes to the queue
• Determine if the current level is an odd or even level, toggle direction before appending to the final answer array.
• Repeat this until the queue is empty

Implementation

python

class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        # If the root node is empty, return an empty list
        if not root:
            return []

        # Initialize the result list
        ans = []
        # Initialize the queue, storing nodes of the current level
        queue = [root]
        # Flag variable, controls whether to invert the node values of the current level
        even = False

        # While queue is not empty, keep processing
        while queue:
            # Store nodes of the next level
            nxt = []
            # Store values of nodes in the current level
            vals = []

            # Traverse the current level's nodes
            for node in queue:
                # Add current node value to vals list
                vals.append(node.val)

                # If left child exists, append it to next level's queue
                if node.left:
                    nxt.append(node.left)
                
                # If right child exists, append it to next level's queue
                if node.right:
                    nxt.append(node.right)
            
            # Update the queue to represent the next level
            queue = nxt
            # Depending on the even flag, decide whether to reverse the values
            # Reverse for even levels, keep original order for odd levels
            ans.append(vals[::-1] if even else vals)
            # Flip the flag bit for the next level
            even = not even
        
        # Return the final zigzag level order traversal
        return ans

javascript

/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var zigzagLevelOrder = function(root) {
    if (!root) return [];

    const ans = [];
    let queue = [root];
    let even = false;
    
    while (queue.length) {
        const nxt = [];
        const vals = [];

        for (let node of queue) {
            vals.push(node.val);

            if (node.left) nxt.push(node.left);

            if (node.right) nxt.push(node.right);
        }

        queue = nxt;
        if (even) {
            vals.reverse();
        }

        ans.push(vals);
        even = !even;
    }
    return ans;
};

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(w), where w is the maximum width of the tree

Links

103. Binary Tree Zigzag Level Order Traversal (English)

103. 二叉树的锯齿形层序遍历 (Chinese)