分批的BFS

发表于 | 更新于 | 分类于 ，

今天学了一招，是关于 BFS 分批的搜索的，首先看看模型例题。

引例

给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

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

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

返回其自底向上的层次遍历为：

1
2
3
4
5
[
  [15,7],
  [9,20],
  [3]
]

倒序倒没什么难度，关键是怎么把每一层分开。最简单的思路是在 BFS 的过程中把深度也存储下来。不过还有一个更好的思路，是一次性搜索完一层，代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
vector<vector<int>> levelOrderBottom(TreeNode* root)
{
    vector<vector<int>> ans;
    if (root == nullptr)
        return ans;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty())
    {
        vector<int> vec;
        //注意看这里
        int n = q.size();
        for (int i = 0; i < n; ++i)
        {
            TreeNode *p = q.front(); q.pop();
            vec.push_back(p->val);
            if (p->left)
                q.push(p->left);
            if (p->right)
                q.push(p->right);
        }
        ans.insert(ans.begin(), vec);
    }
    return ans;
}

传统的 BFS 的模板是在每轮的循环中处理队首的结点: 

1
2
3
4
5
6
7
while (!q.empty())
{
    auto n = q.front(); q.pop();
    //Do Someting
    q.push(n.left);
    q.push(n.right);
}

而在这里，我们在每次的循环中直接把当前所有结点出队，处理整个一层的结点。由于在处理过程中，还会有新的结点加入队列，所以我们首先要获知需要处理的结点有几个。

1
int n = q.size();

这个模板的应用会很广泛的。

例子

在给定的网格中，每个单元格可以有以下三个值之一：

值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。

每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。

返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1

显然，这就是一个一次查找整一层的例子，带入模板，代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
int orangesRotting(vector<vector<int>> &grid)
{
    int dr[4] = {0, -1, 0, 1};
    int dc[4] = {-1, 0, 1, 0};
    int row = grid.size(), col = grid[0].size(), i, j;
    int count = 0, res = 0; //橘子总数量, 分钟数
    queue<int> qu;
    for (i = 0; i < row; ++i)
    {
        for (j = 0; j < col; ++j)
        {
            count += (grid[i][j] > 0);
            if (grid[i][j] == 2)
                qu.push(i * col + j);
        }
    }
    if (count == qu.size())
        return 0;
    while (!qu.empty())
    {
        int size = qu.size();
        res++;
        while (size--)
        {
            int f = qu.front();
            qu.pop();
            count--;
            for (i = 0; i < 4; ++i)
            {
                int ir = f / col + dr[i];
                int ic = f % col + dc[i];
                if (ir >= 0 && ir < row && ic >= 0 &&
                    ic < col && grid[ir][ic] == 1)
                {
                    grid[ir][ic] = 2;
                    qu.push(ir * col + ic);
                }
            }
        }
    }
    return count == 0 ? res - 1 : -1;
}