103. Binary Tree Zigzag Level Order Traversal

Description:

Given the root of a binary tree, return the zigzag level order traversal of its nodes' values. (i.e., from left to right, then right to left for the next level and alternate between).

# 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

'''
[1] using two stack)

idea::
1. direction(left to right or right to left) is zigzag
2. one stack for left to right, the other stack for right to left

code::
(below)

-T/C: O(n)
-S/C: O(n) # for two stack
'''


class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        ans=[]
        if not root:
            return ans
        
        l2r_stack=[]
        r2l_stack=[]
        
        dir=0
        
        r2l_stack.append(root)
        while l2r_stack or r2l_stack:
            if dir%2==0:
                size=len(r2l_stack)
                tmp=[]
                for i in range(size):
                    cur=r2l_stack.pop()
                    tmp.append(cur.val)
                    
                    if cur.left:
                        l2r_stack.append(cur.left)
                    if cur.right:
                        l2r_stack.append(cur.right)
                ans.append(tmp[:])
                
            else:
                size=len(l2r_stack)
                tmp=[]
                for i in range(size):
                    cur=l2r_stack.pop()
                    tmp.append(cur.val)
                    if cur.right:
                        r2l_stack.append(cur.right)
                    if cur.left:                        
                        r2l_stack.append(cur.left)
                ans.append(tmp[:])
            dir+=1
        return ans