【题目描述】

层序遍历是典型的广度优先应用，借助队列实现。可以使用python中collections.deque库，当然也可以不用只用简单的list也ok。看示例中结果的形式，不同层次需要放在不同列表中，因此我们必定要对每个节点属于的层次进行判断，相同层则放在同一列表，统一放入结果中。只要注意这一点，看代码就很直观了。

时间复杂度，空间复杂度都是为线性的，因为只访问每个节点一次。

【源代码】

from collections import deque
class Solution:
   def levelOrder(self, root: TreeNode) -> List[List[int]]:
       if not root:return 
       queue=deque([(1,root)])
       re=[]
       output=[]
       lastdepth=1
       while queue:
           depth,node=queue.popleft()
           if not node:continue
           if not lastdepth==depth:
               re.append(output)
               output=[]
           output.append(node.val)
           queue.append([depth+1,node.left]) 
           queue.append([depth+1,node.right]) 
           lastdepth=depth
       re.append(output)
       return re
复制代码