102. 二叉树的层次遍历

102. 二叉树的层次遍历

题目描述

给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。

例如:
给定二叉树: [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
返回其层次遍历结果：

[
  [3],
  [9,20],
  [15,7]
]

典型的 BFS

Python3

class Solution:
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root : return []
        result = []
        queue = collections.deque()
        queue.append(root)
        
        # 树，所以省略
        # visited = set(root)
        
        # BFS模版 ，queue 不为空，popleft
        while queue:
            level_size = len(queue)
            current_level = [] 
            
            for _ in range(level_size):
                # 取 Queue 头元素 当前层，再添加节点
                node = queue.popleft()
                current_level.append(node.val)
                if node.left:  queue.append(node.left)
                if node.right: queue.append(node.right)
            result.append(current_level)
        return result