队列 + 宽搜（BFS）

作者：知新_RL | 2024-07-01 16:31:10

踩

队列 + 宽搜（BFS）

例题一

解法：

算法思路：

层序遍历即可~ 仅需多加⼀个变量，⽤来记录每⼀层结点的个数就好了。

解法（层序遍历）：

算法思路：

在正常的层序遍历过程中，我们是可以把⼀层的结点放在⼀个数组中去的。既然我们有这个数组，在合适的层数逆序就可以得到锯⻮形层序遍历的结果。

解法（层序遍历）：

算法思路：

1. 第⼀种思路（会超过内存限制）：

既然统计每⼀层的最⼤宽度，我们优先想到的就是利⽤层序遍历，把当前层的结点全部存在队列⾥

⾯，利⽤队列的⻓度来计算每⼀层的宽度，统计出最⼤的宽度。但是，由于空节点也是需要计算在内的。因此，我们可以选择将空节点也存在队列⾥⾯。这个思路是我们正常会想到的思路，但是极端境况下，最左边⼀条⻓链，最右边⼀条⻓链，我们需要存⼏亿个空节点，会超过最⼤内存限制。

2. 第⼆种思路（利⽤⼆叉树的顺序存储 - 通过根节点的下标，计算左右孩⼦的下标）：

依旧是利⽤层序遍历，但是这⼀次队列⾥⾯不单单存结点信息，并且还存储当前结点如果在数组中存储所对应的下标（在我们学习数据结构 - 堆的时候，计算左右孩⼦的⽅式）。这样我们计算每⼀层宽度的时候，⽆需考虑空节点，只需将当层结点的左右结点的下标相减再加 1 即可。

但是，这⾥有个细节问题：如果⼆叉树的层数⾮常恐怖的话，我们任何⼀种数据类型都不能存下下标的值。但是没有问题，因为

• 我们数据的存储是⼀个环形的结构；

• 并且题⽬说明，数据的范围在 int 这个类型的最⼤值的范围之内，因此不会超出⼀圈；

• 因此，如果是求差值的话，我们⽆需考虑溢出的情况。

解法（bfs）：

算法思路：

层序遍历过程中，在执⾏让下⼀层节点⼊队的时候，我们是可以在循环中统计出当前层结点的最⼤值的。因此，可以在 bfs 的过程中，统计出每⼀层结点的最⼤值。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/777052