"Optimal Zigzag Level Order Traversal"
Intuition\nThe problem asks us to perform a zigzag (or spiral) level order traversal of a binary tree. This means traversing the tree level by level but alterna
# Intuition\nThe problem asks us to perform a zigzag (or spiral) level order traversal of a binary tree. This means traversing the tree level by level but alternating the direction at each level:\n\nAt the first level, we traverse from left to right.\nAt the second level, we traverse from right to left.\nWe continue alternating the traversal direction for subsequent levels.\nTo achieve this, we can modify a standard Breadth-First Search (BFS) approach, where we use a queue to process nodes level by level, and adjust how we store the nodes\' values based on the current direction.\n\n# Approach\n1. Initial Setup:\n\nWe start by checking if the tree is empty. If it is, we return an empty result.\nWe use a queue to store nodes and perform level-order traversal (BFS).\n\n2. Level-by-Level Traversal:\n\nFor each level, we first check the number of nodes at that level (levelSize).\nWe create a temporary vector levelNodeData to hold the values of the nodes at this level.\n\n3. Zigzag Logic:\n\nIf the current level is traversing from left to right, we insert node values in the same order as they are processed.\nIf the current level is traversing from right to left, we insert node values in reverse order.\nThis is achieved by using the index i for left-to-right insertion and levelSize - i - 1 for right-to-left insertion.\n\n4. Queue Maintenance:\n\nAfter processing each node, we push its left and right children (if they exist) into the queue, so they can be processed in the next level.\n\n5. Alternate Direction:\n\nAfter each level, we toggle the leftToRight flag to switch between left-to-right and right-to-left traversal for the next level.\nFinal Step:\n\nOnce all levels are processed, the result vector contains the zigzag level order traversal of the tree.\n\n\n# Complexity\n* Time Complexity: O(n)\nWe process each node exactly once, and for each node, we perform constant-time operations such as queue insertion and accessing its children. Therefore, the time complexity is O(n), where n is the number of nodes in the tree.\n* Space Complexity: O(n)\nThe space complexity is dominated by the size of the queue. In the worst case, the queue can hold nodes from the largest level of the tree, which occurs when the tree is a balanced binary tree. Thus, the space complexity is O(n), where n is the number of nodes.\n# Code\n```cpp []\n/**\n * Definition for a binary tree node.\n * struct TreeNode {\n *     int val;\n *     TreeNode *left;\n *     TreeNode *right;\n *     TreeNode() : val(0), left(nullptr), right(nullptr) {}\n *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}\n *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}\n * };\n */\nclass Solution {\npublic:\n    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {\n        // Result vector to store nodes in zigzag order\n        vector<vector<int>> zigzagList;\n\n        // If the root is NULL, return an empty result\n        if (root == NULL) return zigzagList;\n\n        // Queue to store nodes for level-order traversal\n        queue<TreeNode*> pendingNodes;\n        pendingNodes.push(root);\n\n        // Flag to alternate between left-to-right and right-to-left order\n        bool leftToRight = true;\n\n        // Loop until there are nodes to process\n        while (!pendingNodes.empty()) {\n            // Get the number of nodes at the current level\n            int levelSize = pendingNodes.size();\n            \n            // Vector to store the current level\'s node values\n            vector<int> levelNodeData(levelSize);\n\n            // Process each node at the current level\n            for (int i = 0; i < levelSize; i++) {\n                TreeNode* frontNode = pendingNodes.front();\n                pendingNodes.pop();\n\n                // If leftToRight is true, fill values from left to right\n                if (leftToRight) {\n                    levelNodeData[i] = frontNode->val;\n                } \n                // Otherwise, fill values from right to left\n                else {\n                    levelNodeData[levelSize - i - 1] = frontNode->val;\n                }\n\n                // Add left and right children to the queue if they exist\n                if (frontNode->left != NULL) pendingNodes.push(frontNode->left);\n                if (frontNode->right != NULL) pendingNodes.push(frontNode->right);\n            }\n\n            // After processing the current level, add the values to the result\n            zigzagList.push_back(levelNodeData);\n\n            // Flip the direction for the next level\n            leftToRight = !leftToRight;\n        }\n\n        return zigzagList;\n    }\n};\n\n```
['C++']