leetcode-bt

103. Binary Tree Zigzag Level Order Traversal.py

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    """
    Thought Process
    
        1  depth=1
       / \
      2.  3  depth=2
     ->[[1],[3,2]]
     
        1
       / \
      2   3
     /\   /\
    4  6 7  8
     ->[[1],[3,2],[4,6,7,8]]
     
     The below is tricky part:
         if depth % 2== 0:
            # even
            from left to right
         else:
            # odd
            from right to left
    """
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        """
        T:O(n) but it's two passes since each node is only visited once.
        S:O(n)
        """
        if not root:
            return []
        
        zigzag_level_order = []
        q = collections.deque([(root, 1)])
        while len(q) != 0:
            cur_node, depth = q.popleft()
            if cur_node.left:
                q.append((cur_node.left, depth+1))
            if cur_node.right:
                q.append((cur_node.right, depth+1))
            while len(zigzag_level_order) < depth:
                zigzag_level_order.append([])
            zigzag_level_order[depth-1].append(cur_node.val)
            
        return [level_order_ls[::-1] if depth%2==1 else level_order_ls for depth, level_order_ls in enumerate(zigzag_level_order)]