103. Binary Tree Zigzag Level Order Traversal - cocoder39/coco39_LC GitHub Wiki

class Solution:
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        queue = collections.deque()
        left_to_right = True
        if root:
            queue.append(root)
        
        res = []
        while queue:
            sz = len(queue)
            level = collections.deque()
            for i in range(sz):
                node = queue.popleft()
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
                if left_to_right:
                    level.append(node.val)
                else:
                    level.appendleft(node.val)
                
            left_to_right = not left_to_right
            res.append(level)
        
        return res

vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> res;
        bool left2right = true; 
        queue<TreeNode*> q;
        if (root) {
            q.push(root);
        }
        
        while (! q.empty()) {
            int sz = q.size();
            vector<int> level(sz);
            
            for (int i = 0; i < sz; i++) {
                TreeNode* node = q.front();
                q.pop();
                left2right ? level[i] = node->val : level[sz - 1 - i] = node->val;
                
                if (node->left) {
                    q.push(node->left);
                }
                if (node->right) {
                    q.push(node->right);
                }
            }
            res.push_back(level);
            left2right ^= 1;
        }
        return res;
    }