Leetcode # 103. Binary Tree Zigzag Level Order Traversal

Problem

https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/

Solution

Time Complexity: O(len(tree))
Space Complexity: O(sqrt(len(tree)))
(The input and output generally do not count towards the space complexity.)

⚠️ deque 不可以使用切片 [::-1] 來逆序

class Solution:
  def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
    curr_level = 0
    curr_level_nodes = collections.deque([root] if root else [])
    nodes = []
    while curr_level_nodes:
      next_level_nodes = collections.deque()
      nodes.append([])
      while curr_level_nodes:
        node = curr_level_nodes.popleft() if curr_level % 2 == 0 else curr_level_nodes.pop()
        nodes[-1].append(node.val)
        for child in [node.left, node.right] if curr_level % 2 == 0 else [node.right, node.left]:
          if child:
            if curr_level % 2 == 0:
              next_level_nodes.append(child)
            else:
              next_level_nodes.appendleft(child)
      curr_level += 1
      curr_level_nodes = next_level_nodes
    return nodes

Last Updated on 2024/04/21 by A1go