越而胜己 / Beyond awesome

Link to problem: https://leetcode.com/problems/binary-tree-level-order-traversal/

This is obviously a BFS problem. Like LC45. Jump Game II, BFS itself is quite easy, but the key is to find the boundaries between two BFS layers in the traversal. Because the BFS in this problem is on an actual graph (tree), we need to maintain a queue q for BFS.

Before we begin BFS, q has one element root, according to the BFS algorithm; and level 0 happens to contain just root. After visiting root, q now has two elements: root.left and root.right, and these are the elements in level 1.

So, to figure out the boundary between levels, after traversing the previous level, count how many nodes are in this level (should be len(q)). Then we do the BFS loop len(q) times to finish iterating this level.

This method should also apply to generic graphs, with only slight modification of maintaining a discovered set to keep track of visited vertices.

显然这是一道能用 BFS 解决的题目。与 LC45. Jump Game II 一样,BFS 本身很简单,关键在于如何找到层与层之间的边界。由于这是一道标准的图(树)上 BFS,我们需要维护一个队列 q 来进行 BFS。

在循环开始前,根据 BFS 算法,q 只有一个元素 root,而 root 即是第 0 层的唯一元素。访问 root 后,第 0 层遍历完毕,而 root.leftroot.right 被放到了 q 中,此时 q 中有两个元素,而第 1 层正有这两个元素。

所以获得每层边界的方法是,在结束上一层的遍历之后先数这一层有多少个元素需要访问,即 len(q)。然后进行 len(q) 次循环后结束本层遍历。

这种方法对于普通的图来说也可以适用,只是需要使用一个 discovered 集合来记录已经访问过的顶点,防止重复访问。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

from collections import deque

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        levels = []
        q = deque([root])
        while q:
            level = []
            level_len = len(q)
            for i in range(level_len):
                u = q.popleft()
                level.append(u.val)
                if u.left:
                    q.append(u.left)
                if u.right:
                    q.append(u.right)
            levels.append(level)
        return levels
BFS Solution