Binary Tree Zigzag Level Order Traversal [C++]
IntuitionThe problem involves traversing a binary tree in a zigzag (alternating) order, level by level. This can be thought of as a variation of the standard le
# Intuition
The problem involves traversing a binary tree in a zigzag (alternating) order, level by level. This can be thought of as a variation of the standard level-order traversal with the additional requirement of reversing the order of nodes at alternate levels.

# Approach
1. **Use a Queue for BFS Traversal**: 
   - Perform a standard breadth-first search (BFS) using a queue to traverse the tree level by level.
2. **Track Direction**: 
   - Use a boolean variable `leftToRight` to alternate the order of node insertion for each level.
   - If `leftToRight` is `true`, append nodes left to right. Otherwise, append nodes right to left.
3. **Reverse Nodes for Zigzag**: 
   - Depending on the direction, either insert nodes directly into the result vector or insert them in reverse order for that level.

# Complexity
- **Time Complexity**:  
  $$O(n)$$, where \(n\) is the number of nodes in the tree, as each node is processed exactly once.
  
- **Space Complexity**:  
  $$O(w)$$, where \(w\) is the maximum width of the tree, which is the largest number of nodes at any level. This space is used by the queue during BFS.

# Code
```cpp
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        if (!root) return {};
        vector<vector<int>> result;
        queue<TreeNode*> q;
        q.push(root);
        bool leftToRight = true;

        while (!q.empty()) {
            int levelSize = q.size();
            vector<int> level(levelSize);
            for (int i = 0; i < levelSize; ++i) {
                TreeNode* node = q.front();
                q.pop();
                int index = leftToRight ? i : (levelSize - 1 - i);
                level[index] = node->val;

                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            leftToRight = !leftToRight;
            result.push_back(level);
        }

        return result;
    }
};
```
['C++']