[LeetCode] 102. Binary Tree Level Order Traversal_Medium tag: BFS

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]

]

这个题目非常明显的适用BFS, 从root, 依次将每一层append进入ans里, 只是要注意的就是如果判断哪个是在哪一层呢, 这里用到的方法是利用size of queue, 每次得到的size就是该层的数目, 
每层用一个temp list去存每一层的元素, 结束之后append进入ans中. 

1. Constraints
  1) tree 可以为empty, 所以edge case 为root == None

2. Ideas

    BFS   T: O(n)     S: O(n)    n is number of nodes in the tree

3. code

import collections

class Solution:

    def levelOrder(self, root):

        """

        :type root: TreeNode

        :rtype: List[List[int]]

        """

        if not root: return []

        ans, queue = [], collections.deque([root])

        while queue:

            size, level = len(queue), []

            for _ in range(size):

                node = queue.popleft()

                level.append(node.val)

                if node.left:

                    queue.append(node.left)

                if node.right:

                    queue.append(node.right)

            ans.append(level)

        return ans

4. Test cases

1) None   =>   []

2) [1]    =>  [[1]]

3)

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]

]