103. Binary Tree Zigzag Level Order Traversal

Description

This problem involves performing a level-order traversal of a binary tree in a zigzag pattern, alternating directions between levels.

Intuition

To achieve the zigzag traversal:

• Use a queue for level-order traversal.
• Maintain a flag to track the direction (left to right or right to left) for each level.
• Adjust the insertion order of node values based on the direction flag.

Approach

1. Initialization: Start with an empty result list and a queue initialized with the root node.
2. Level Order Traversal: - Iterate over the nodes in the queue for each level. - Depending on the direction flag, append or insert node values into the current level list. - Enqueue child nodes (left and right) for the next level.
3. Direction Control: Toggle the direction flag after processing each level to alternate between left to right and right to left.
4. Completion: Once the queue is empty, all levels have been processed. Return the result list containing all levels.

Complexity

Time Complexity:

O(n), where n is the number of nodes in the binary tree. Each node is processed exactly once.

Space Complexity:

O(n), in the worst case (completely unbalanced tree), the queue can contain all nodes at the maximum width of the tree.

Code

C++

class Solution {
public:
    vector> zigzagLevelOrder(TreeNode* root) {
        if (!root) return {};
        vector> result;
        queue queueNodes;
        queueNodes.push(root);
        bool leftToRight = true;
        
        while (!queueNodes.empty()) {
            int size = queueNodes.size();
            vector level(size);
            
            for (int i = 0; i < size; ++i) {
                TreeNode* node = queueNodes.front();
                queueNodes.pop();
                
                int index = leftToRight ? i : size - 1 - i;
                level[index] = node->val;
                
                if (node->left) queueNodes.push(node->left);
                if (node->right) queueNodes.push(node->right);
            }
            
            result.push_back(level);
            leftToRight = !leftToRight;
        }
        
        return result;
    }
};

Python

class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        
        result = []
        queue = deque([root])
        left_to_right = True
        
        while queue:
            level_size = len(queue)
            level_values = []
            
            for _ in range(level_size):
                node = queue.popleft()
                
                if left_to_right:
                    level_values.append(node.val)
                else:
                    level_values.insert(0, node.val)
                
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            
            result.append(level_values)
            left_to_right = not left_to_right
        
        return result

Java

class Solution {
    public List> zigzagLevelOrder(TreeNode root) {
        List> result = new ArrayList<>();
        if (root == null) return result;
        
        Queue queue = new LinkedList<>();
        queue.offer(root);
        boolean leftToRight = true;
        while (!queue.isEmpty()) {
            int size = queue.size();
            List level = new ArrayList<>(size);
            
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                
                if (leftToRight) {
                    level.add(node.val);
                } else {
                    level.add(0, node.val);
                }
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            result.add(level);
            leftToRight = !leftToRight;
        }
        return result;
    }
}

JavaScript

var zigzagLevelOrder = function(root) 
{
    if (!root) return [];
    let stackQueue = [root];
    let result = [];
    let level = 1;
    
    while (stackQueue.length > 0) {
        const isLtoR = level % 2 === 1;
        const subLength = stackQueue.length;
        const subList = [];
        for (let i = 0; i < subLength; i++) 
        {
            let node= stackQueue.shift();
            if (isLtoR) {
                subList.push(node.val);
            } else {
                 subList.unshift(node.val);
            }
            if (node.left) stackQueue.push(node.left);
            if (node.right) stackQueue.push(node.right);
        }
        level++;
        result.push(subList);
    }
    return result;
};