ds之bfs

发表于 | 分类于 | 阅读次数:
字数统计: 102 | 阅读时长 ≈ 1

广度优先搜索

本质上就是队列queue的应用

在写代码的时候 也可以使用双端队列

以leetcode 102题 层次遍历为例子 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
    def levelOrder(self, root):
        if not root:
            return []

        res = []
        queue = collections.deque()
        queue.append(root)

        # visited = set(root)

        while queue:
            level_size = len(queue)
            current_size = []

            for _ in range(level_size):
                node = queue.popleft()
                current_level.append(node.val)
                if node.left: queue.append(node.left)
                if node.right: queue.append(node.right)

            res.append(current_level)

        return res