当前位置:   article > 正文

队列 + 宽搜(BFS)

队列 + 宽搜(BFS)

例题一

解法:
算法思路:
层序遍历即可~ 仅需多加⼀个变量,⽤来记录每⼀层结点的个数就好了。

例题二

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

例题三

解法(层序遍历):
算法思路:
1. 第⼀种思路(会超过内存限制):
既然统计每⼀层的最⼤宽度,我们优先想到的就是利⽤层序遍历,把当前层的结点全部存在队列⾥
⾯,利⽤队列的⻓度来计算每⼀层的宽度,统计出最⼤的宽度。但是,由于空节点也是需要计算在内的。因此,我们可以选择将空节点也存在队列⾥⾯。这个思路是我们正常会想到的思路,但是极端境况下,最左边⼀条⻓链,最右边⼀条⻓链,我们需要存⼏亿个空节点,会超过最⼤内存限制。
2. 第⼆种思路(利⽤⼆叉树的顺序存储 - 通过根节点的下标,计算左右孩⼦的下标):
依旧是利⽤层序遍历,但是这⼀次队列⾥⾯不单单存结点信息,并且还存储当前结点如果在数组中存储所对应的下标(在我们学习数据结构 - 堆的时候,计算左右孩⼦的⽅式)。这样我们计算每⼀层宽度的时候,⽆需考虑空节点,只需将当层结点的左右结点的下标相减再加 1 即可。
但是,这⾥有个细节问题:如果⼆叉树的层数⾮常恐怖的话,我们任何⼀种数据类型都不能存下下标的值。但是没有问题,因为
我们数据的存储是⼀个环形的结构;
并且题⽬说明,数据的范围在 int 这个类型的最⼤值的范围之内,因此不会超出⼀圈;
因此,如果是求差值的话,我们⽆需考虑溢出的情况。

例题四

解法(bfs):
算法思路:
层序遍历过程中,在执⾏让下⼀层节点⼊队的时候,我们是可以在循环中统计出当前层结点的最⼤值的。因此,可以在 bfs 的过程中,统计出每⼀层结点的最⼤值。
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/知新_RL/article/detail/777052
推荐阅读
相关标签
  

闽ICP备14008679号