Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).


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

    3
   / \
  9  20
    /  \
   15   7



return its level order traversal as:

[
  [3],
  [9,20],
  [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 levelOrder(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 levelOrder(self, root):
         """
         :type root: TreeNode
         :rtype: List[List[int]]
         """
         queue, res = [root], []
         while any(queue):
             tmp = []
             for _ in range(len(queue)):
                 node = queue.pop(0)
                 tmp.append(node.val)
                 if node.left:
                     queue.append(node.left)
                 if node.right:
                     queue.append(node.right)
             res.append(tmp)
         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 levelOrder(self, root):
         """
         :type root: TreeNode
         :rtype: List[List[int]]
         """
         res = []
         level = [root]
 
         while root and level:
             res.append([node.val for node in level])
             level = [child for node in level for child in (node.left, node.right) if child]
 
         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 traverse(self, root, ordered, level=0):
         if root.left:
             self.traverse(root.left, ordered, level=level+1)
         for create in range(level-len(ordered)+1):
             ordered.append([])
         ordered[level].append(root.val)
         if root.right:
             self.traverse(root.right, ordered, level=level+1)
     def levelOrder(self, root):
         """
         :type root: TreeNode
         :rtype: List[List[int]]
         """
         if not root:
             return []
         ordered = [[]]
         self.traverse(root, ordered, level=0)
         return ordered

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def levelOrder(self, root):
         """
         :type root: TreeNode
         :rtype: List[List[int]]
         """
         result = []
         if not root:
             return result
         curr_level = [root]
         while curr_level:
             level_result = []
             next_level = []
             for temp in curr_level:
                 level_result.append(temp.val)
                 if temp.left:
                     next_level.append(temp.left)
                 if temp.right:
                     next_level.append(temp.right)
             result.append(level_result)
             curr_level = 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 levelOrder(self, root):
         """
         :type root: TreeNode
         :rtype: List[List[int]]
         """
         if not root:
             return []
         q = [(0, root)]
         res = [[]]
         while q:
             level, node = q.pop()
             if level > len(res) - 1:
                 res.append([node.val])
             else:
                 res[level] += [node.val]
             if node.left:
                 q.insert(0,(level + 1, node.left))
             
             if node.right:
                 q.insert(0, (level + 1, node.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 levelOrder(self, root):
         """
         :type root: TreeNode
         :rtype: List[List[int]]
         """
         if root == None:
             return []
         
         queue = collections.deque()
         
         reslist = []
         
         queue.append(root)
         
         while queue:
             level = []
             for i in range(len(queue)):
                 node = queue.popleft()
                 level.append(node.val)
                 if node.left != None:
                     queue.append(node.left)
                 if node.right != None:
                     queue.append(node.right)
             reslist.append(level)
         
         return reslist

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def levelOrder(self, root):
         """
         :type root: TreeNode
         :rtype: List[List[int]]
         """
         if root is None:
             return []
         queue = [root]
         result = []
         while len(queue) > 0:
             k = len(queue)
             sublist = []
             for i in range(k):
                 node = queue.pop(0)
                 sublist.append(node.val)
                 if node.left is not None:
                     queue.append(node.left)
                 if node.right is not None:
                     queue.append(node.right)
             result.append(sublist)
         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 levelOrder(self, root):
         """
         :type root: TreeNode
         :rtype: List[List[int]]
         """
         if root is None:
             return []
         vals = []
         self.traverse(root, vals, 0)
         return vals
         
     def traverse(self, node, vals, depth):
         if node is None:
             return
         self.traverse(node.left, vals, depth + 1)
         while len(vals) - 1 < depth:
             #print(depth)
             vals.append([])
         vals[depth].append(node.val)   
         self.traverse(node.right, vals, depth + 1)
         return
 
             
 
         
         

# 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 levelOrder(self, root):
         """
         :type root: TreeNode
         :rtype: List[List[int]]
         """
         if root == None:
             return []
         ret = []
         bfs = []
         bfs.append(root)
         cur = 0
         nextl = len(bfs)
         
         while (cur<nextl):
             cur_level = []
             for i in range(cur,nextl):
                 cur_node = bfs[i]
                 if cur_node.left != None:
                     bfs.append(cur_node.left)
                 if cur_node.right != None:
                     bfs.append(cur_node.right)            
                 cur_level.append(bfs[i].val)
             ret.append(cur_level)
             cur,nextl = nextl, len(bfs)
         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 levelOrder(self, root):
         """
         :type root: TreeNode
         :rtype: List[List[int]]
         """
         res = []
         if not root:
             return res
         
         stack = [root]
         row = [root.val]
         
         while stack:
             res += [row]
             tempstack = []
             temprow = []
             
             for n in stack:
                 if n.left:
                     tempstack += [n.left]
                     temprow += [n.left.val]
                 if n.right:
                     tempstack += [n.right]
                     temprow += [n.right.val]
             row = temprow
             stack = tempstack
         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 levelOrder(self, root):
         """
         :type root: TreeNode
         :rtype: List[List[int]]
         """
         visited = []
         queue = collections.deque()
         if not root:
             return []
         level = []
         currLv = 1
         queue.append((root, currLv))
         hights = {}
         while queue:
             node, currLv = queue.popleft()
             if currLv not in hights:
                 hights[currLv] = [node.val]
             else:
                 hights[currLv].append(node.val)
             currLv += 1
             if node.left:
                 queue.append((node.left, currLv))
             if node.right:
                 queue.append((node.right, currLv))
             
         return [lv for lv in hights.values()]

from queue import Queue
 
 # Definition for a binary tree node.
 # class TreeNode(object):
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution(object):
     def levelOrder(self, root):
         """
         :type root: TreeNode
         :rtype: List[List[int]]
         """
         results = []
         if root is None:
             return results
         q = Queue()
         q.put(root)
         while not q.empty():
             size  = q.qsize()
             sublist = []
             for i in range(size):
                 node = q.get()
                 if node.left is not None:
                     q.put(node.left)
                 if node.right is not None:
                     q.put(node.right)
                 sublist.append(node.val)
             results.append(sublist)
         return results
             

# 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 levelOrder(self, root):
         """
         :type root: TreeNode
         :rtype: List[List[int]]
         """
         q = queue.Queue()
         q.put(root)
         curNode = root
         levels = []
         while curNode is not None and not q.empty():
             level = []
             newQ = queue.Queue()
             while not q.empty():
                 curNode = q.get()
                 level.append(curNode.val)
                 if curNode.left is not None:
                     newQ.put(curNode.left)
                 if curNode.right is not None:
                     newQ.put(curNode.right)
             levels.append(level)
             q = newQ
         return levels

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def levelOrder(self, root):
         """
         :type root: TreeNode
         :rtype: List[List[int]]
         """
         from queue import Queue
         
         q1, q2 = Queue(), Queue()
         q1.put(root)
         ret = []
         
         while (q1.empty() and not q2.empty()) or (not q1.empty() and q2.empty()):
             rst = []
             if not q1.empty():
                 # print("q1 not empty")
                 while not q1.empty():
                     node = q1.get()
                     if not node:
                         continue
                     else:
                         # print("q1:", node.val)
                         rst.append(node.val)
                         q2.put(node.left)
                         q2.put(node.right)
             else:
                 # print("q2 not empty")
                 while not q2.empty():
                     node = q2.get()
                     if not node:
                         continue
                     else:
                         # print("q2:", node.val)
                         rst.append(node.val)
                         q1.put(node.left)
                         q1.put(node.right) 
             if len(rst) > 0:
                 ret.append(rst)
         return ret
                 


# 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(object):
     def levelOrder(self, root):
         """
         :type root: TreeNode
         :rtype: List[List[int]]
         """
         if not root:
             return []
         
         q = queue.Queue()
         q.put(root)
         ret = []
         while not q.empty():
             nq = queue.Queue()
             level = []
             while not q.empty():
                 node = q.get()
                 level.append(node.val)
                 
                 if node.left:
                     nq.put(node.left)
                 if node.right:
                     nq.put(node.right)
             ret.append(level)
             q = nq
         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 levelOrder(self, root):
         """
         :type root: TreeNode
         :rtype: List[List[int]]
         """
         if root is None:
             return []
         q = [(root, 0)]
         res = []
         prev_lvl = -1
         while q:
             current, lvl = q[0]
             q.pop(0)
             if lvl > prev_lvl:
                 res.append([current.val])
             else:
                 res[-1].append(current.val)
             prev_lvl = lvl
             if current.left:
                 q.append((current.left, lvl + 1))
             if current.right:
                 q.append((current.right, lvl + 1))
         return res