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


For example:
Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7



return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

Difficulty: interview

Starter code:

# 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:
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        

Solutions:
# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def zigzagLevelOrder(self, root):
         """
         :type root: TreeNode
         :rtype: List[List[int]]
         """
         if root is None:
             return []
         
         res = []
         level_num = 1
         level = [root]
         
 
         while len(level) != 0:
             level_size = len(level)
             level_res = [None]*level_size
             for i in range(level_size):
                 curr = level.pop(0)
                 level_res[i] = curr.val
                 if curr.left is not None:
                     level.append(curr.left)
                 if curr.right is not None:
                     level.append(curr.right)
             if level_num % 2:
                 res.append(level_res)
             else:
                 level_res.reverse()
                 res.append(level_res)
             level_num += 1
             
         return res
         
         
         
         

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def zigzagLevelOrder(self, root):
         """
         :type root: TreeNode
         :rtype: List[List[int]]
         """
         from collections import deque
         mydeque = deque()
         ret = []
         if root == None:
             return []
         mydeque.append(root)
         reverseflag = False
         while len(mydeque) != 0:
             curlist = []
             newdeque = deque()
             width = len(mydeque)
             for _ in range(0, width):
                 node = mydeque.pop()
                 if reverseflag:
                     node.left, node.right = node.right, node.left
                 curlist.append(node.val)
                 if node.left != None:
                     newdeque.append(node.left)
                 if node.right != None:
                     newdeque.append(node.right)
             mydeque = newdeque
             ret.append(curlist)
             reverseflag = not reverseflag
         return ret

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def zigzagLevelOrder(self, root):
         """
         :type root: TreeNode
         :rtype: List[List[int]]
         """
         if not root:
             return []
         
         l = [root]
         r = False
         ret = []
         
         while l:
             values = [node.val for node in l]
             if r:
                 values.reverse()
             ret.append(values)
             tmp = []
             for node in l:
                 if node.left:
                     tmp.append(node.left)
                 if node.right:
                     tmp.append(node.right)
             l = tmp
             r = not r
             
         return ret

class Solution:
     def zigzagLevelOrder(self, root):
         """
         :type root: TreeNode
         :rtype: List[List[int]]
         """
         if root == None:
             return []
         result = []
         queue = []
         queue.append([0, root])
         while len(queue) != 0:
             level, temp = queue.pop(0)
             if len(result) < level + 1:
                 result.append([])
             if level % 2 == 0:
                 result[level].append(temp.val)
             else:
                 result[level].insert(0, temp.val)
             if temp.left:
                 queue.append([level+1, temp.left])
             if temp.right:
                 queue.append([level+1, temp.right])
         return result

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def zigzagLevelOrder(self, root):
         """
         :type root: TreeNode
         :rtype: List[List[int]]
         """
         if not root:
             return []
         
         l = [root]
         r = False
         ret = []
         
         while l:
             values = [node.val for node in l]
             if r:
                 values.reverse()
             ret.append(values)
             tmp = []
             for node in l:
                 if node.left:
                     tmp.append(node.left)
                 if node.right:
                     tmp.append(node.right)
             l = tmp
             r = not r
             
         return ret

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 from collections import deque
 
 class Solution:
     def zigzagLevelOrder(self, root):
         """
         :type root: TreeNode
         :rtype: List[List[int]]
         """
         if not root:
             return []
         q, d, tmp, ret = deque([]), deque([]),[], []
         q.append(root)
         flag = 1
         while(q or d):
             node = q.popleft()
 
             if node: tmp.append(node.val)
             if node.left: d.append(node.left)
             if node.right: d.append(node.right)
             if not len(q):
                 ret.append(tmp[::flag])
                 q = d
                 d = deque([])
                 tmp = []
                 flag = -flag
             
         return ret
                 

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 from collections import defaultdict
 from queue import Queue
 
 class Solution:
   def zigzagLevelOrder(self, root):
     """
     :type root: TreeNode
     :rtype: List[List[int]]
     """
     if not root:
       return []
     node_level = {root: 0}
     level_nodes = defaultdict(lambda: [])
     # Group nodes by level in BFS order
     q = Queue()
     q.put(root)
     level_nodes[0].append(root)
     while not q.empty():
       node = q.get()
       child_level = node_level[node] + 1
       if node.left:
         node_level[node.left] = child_level
         level_nodes[child_level].append(node.left)
         q.put(node.left)
       if node.right:
         node_level[node.right] = child_level
         level_nodes[child_level].append(node.right)
         q.put(node.right)
     # Go through nodes level by level
     level_nodes_pairs = sorted(list(level_nodes.items()))
     result = []
     for (level, nodes) in level_nodes_pairs:
       if level % 2 == 0:
         # Left to right
         result.append([node.val for node in nodes])
       else:
         # Right to left
         result.append([node.val for node in reversed(nodes)])
     return result
     


# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 import queue
 class Solution:
     def zigzagLevelOrder(self, root):
         """
         :type root: TreeNode
         :rtype: List[List[int]]
         """
         if root == None:
             return []
         bfs = queue.Queue()
         ret = []
         flag = 0
         bfs.put(root)
         
         while(bfs.empty()==False):
             cur_list = []
             bfs_len = bfs.qsize()
             for i in range(bfs_len):
                 cur = bfs.get()
                 if cur.left != None:
                     bfs.put(cur.left)
                 if cur.right != None:
                     bfs.put(cur.right)
                 cur_list.append(cur.val)
             if flag == 1:
                 cur_list.reverse()
                 flag = 0
             else:
                 flag = 1
             ret.append(cur_list)
         return ret
                 
         

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 from copy import deepcopy
 class Solution:
     def zigzagLevelOrder(self, root):
         """
         :type root: TreeNode
         :rtype: List[List[int]]
         """
         if not root:
             return []
         left2rightq = [root]
         right2leftq = []
         result = []
         while left2rightq or right2leftq:
             if left2rightq:
                 line = []
                 while left2rightq:
                     tmp = left2rightq.pop(-1)
                     line.append(tmp.val)
                     if tmp.left:
                         right2leftq.append(tmp.left)
                     if tmp.right:
                         right2leftq.append(tmp.right)
                     else:
                         pass
                 result.append(line)
             else:
                 line = []
                 while right2leftq:
                     tmp = right2leftq.pop()
                     line.append(tmp.val)
                     if tmp.right:
                         left2rightq.append(tmp.right)
                     if tmp.left:
                         left2rightq.append(tmp.left)
 
                     else:
                         pass
                 result.append(line)
         return result
                 
         

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 import queue
 class Solution:
     # # 用两个栈
     # def zigzagLevelOrder(self, root):
     #     """
     #     :type root: TreeNode
     #     :rtype: List[List[int]]
     #     """
     #     if (root is None):
     #         return []
     #     s1, s2 = [], []
     #     res = []
     #     level = []
     #     s1.append(root)
     #     deal_s1 = True
     #     while (s1 or s2):
     #         # 下面一行不能写成if(s1)，因为在处理s2时，会向s1中压数据
     #         if (deal_s1):
     #             cur = s1.pop()
     #             level.append(cur.val)
     #             if (cur.left is not None):
     #                 s2.append(cur.left)
     #             if (cur.right is not None):
     #                 s2.append(cur.right)
     #             if (not s1):
     #                 res.append(level[:])
     #                 level = []
     #                 deal_s1 = False
     #         else:
     #             cur = s2.pop()
     #             level.append(cur.val)
     #             if (cur.right is not None):
     #                 s1.append(cur.right)
     #             if (cur.left is not None):
     #                 s1.append(cur.left)
     #             if (not s2):
     #                 res.append(level[:])
     #                 level = []
     #                 deal_s1 = True
     #     return res
                 
     def zigzagLevelOrder(self, root):
         """
         :type root: TreeNode
         :rtype: List[List[int]]
         """
         if (root is None):
             return []
         res = []
         level = []
         q = queue.Queue()
         q.put(root)
         q.put(None)
         reverse = 1
         while (not q.empty()):
             cur = q.get()
             if (cur is None):
                 res.append(level[::reverse])
                 level = []
                 reverse *= -1
                 if (not q.empty()):
                     q.put(None)
             else:
                 level.append(cur.val)
                 if (cur.left is not None):
                     q.put(cur.left)
                 if (cur.right is not None):
                     q.put(cur.right)
         return res
         

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def zigzagLevelOrder(self, root):
         """
         :type root: TreeNode
         :rtype: List[List[int]]
         """
         if root is None:
             return []
         result = []
         current = [root]
         clevel=1
         while current:
             next_level = []
             vals = []
             for node in current:
                 vals.append(node.val)
                 if node.left:
                     next_level.append(node.left)
                 if node.right:
                     next_level.append(node.right)
                     
             if (clevel%2):
                 result.append(vals)
             else:
                 result.append(vals[::-1])
             clevel+=1
             current = next_level
         return result
         

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def zigzagLevelOrder(self, root):
         """
         :type root: TreeNode
         :rtype: List[List[int]]
         """
         if not root:
             return []
         
         cur_level,levelOrder,level=[root],[],1
         while cur_level:
             next_level,vals=[],[]
             for node in cur_level:
                 vals.append(node.val)
                 if node.left:
                     next_level.append(node.left)
                 if node.right:
                     next_level.append(node.right)
             if level%2==1:
                 levelOrder.append(vals)
             else:
                 levelOrder.append(vals[::-1])
             level+=1
             cur_level=next_level
         return levelOrder