"""
32 - I.
12 ， 。
:
: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
：
[3,9,20,15,7]
：
<= 1000
"""
"""
：
： ， [] ；
： res = [] ， queue = [root] ；
BFS ： queue ；
： ， node；
： node.val tmp ；
： node （ ） ， （ ） queue ；
： 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) :
"""
:param root: TreeNode
:return: List[int]
"""
# BFS iteration, use queue
# time: O(N) N: the number of the nodes
# space: O(N) N: the length of res, traverse all the nodes
# empty
if not root: return []
queue = [root]
res = []
while queue:
# when queue is not empty, pop node from the head of queue
node = queue.pop(0)
# put the value of the node into res
res.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return res
#
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(5)
s = Solution()
print(s.levelOrder(root))
# ：
s = Solution()
root = TreeNode([])
print(s.levelOrder(root))