Reverse Odd Levels of Binary Tree

lcpy gen -n 2415   # by problem number
lcpy gen -s reverse_odd_levels_of_binary_tree   # by problem name

Input: root = [2,3,5,8,13,21,34]
Output: [2,5,3,8,13,21,34]
Explanation:
The tree has only one odd level.
The nodes at level 1 are 3, 5 respectively, which are reversed and become 5, 3.

Input: root = [7,13,11]
Output: [7,11,13]
Explanation:
The nodes at level 1 are 13, 11, which are reversed and become 11, 13.

Input: root = [0,1,2,0,0,0,0,1,1,1,1,2,2,2,2]
Output: [0,2,1,0,0,0,0,2,2,2,2,1,1,1,1]
Explanation:
The odd levels have non-zero values.
The nodes at level 1 were 1, 2, and are 2, 1 after the reversal.
The nodes at level 3 were 1, 1, 1, 1, 2, 2, 2, 2, and are 2, 2, 2, 2, 1, 1, 1, 1 after the reversal.

from collections import deque

from leetcode_py import TreeNode


class Solution:
    # Time: O(n)
    # Space: O(w) for the level queue, w = 2^depth at the deepest level
    def reverse_odd_levels(self, root: TreeNode[int] | None) -> TreeNode[int] | None:
        if root is None:
            return None
        queue: deque[TreeNode[int]] = deque([root])
        depth = 0
        while queue:
            level = list(queue)
            if depth % 2 == 1:
                left = 0
                right = len(level) - 1
                while left < right:
                    level[left].val, level[right].val = level[right].val, level[left].val
                    left += 1
                    right -= 1
            queue = deque(
                child for node in level for child in (node.left, node.right) if child is not None
            )
            depth += 1
        return root