🎨 Try our Free AI Image Generation Feature

103. Binary Tree Zigzag Level Order Traversal

avatar
Dare2Solve

11 months ago

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;
};