leetcode102.Binary Tree Level Order Traversal

原题链接https://leetcode.com/problems/binary-tree-level-order-traversal/

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]
]
常规层序遍历，用一个队列保存同级的结点，在遍历时将下一层结点入队，同时用count统计下一层结点数量，当本层遍历数量自增到上次保留的count值后，本层遍历结束，进入下一层结点，同时更新count值，得到的本层res，进入res_stack。直到队列为空，输出res_stack。

# 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
from collections import deque
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        
        deques = deque()
        res_stack = []
        deques.append(root)
        count = 1
        while deques:
            res = []
            n = count
            count = 0
            i = 0
            while i < n:
                item = deques.popleft()
                res.append(item.val)
                i += 1
                if item.left:
                    count += 1
                    deques.append(item.left)
                if item.right:
                    count += 1
                    deques.append(item.right)
            res_stack.append(res)
        return res_stack