登录
  • #刷题

关于‌‌‌‌‍‍‌‍‌‌‍‍‍‌‌‍‍‍‍‌‍‌‍‍‍‍‍‌‍‌‍‍BFS创建队列后,放入元素问题。。。。。。。。。。。。。

ATPtennis
595
10
我知道在执行BFS时,是先进先出的原则,第一个拿出来,然后找邻居,然后把邻居放回。

比如 102. Binary Tree Level Order Traversal 这道题。

我的问题是,在执行BFS之前,以二叉树为例,我们要执行queue.append(root)。

此时我们首先是把root全部放入队列,这时候root里 root = [3,9,20,null,null,15,7] 这些数据可是全进队列了。

然后下面我们把最左边的3 popleft以后,找到邻居9和20,这时候把9和20放回队列,可是这时候队列中已经有9和20了啊,难道又放一遍?

注意:这题和 994. Rotting Oranges 橘子那道题有不一样的地方,如果起始我们有2个烂橘子,这时候你遍历整个二维数组,以其中一个烂橘子作为起始对象,找到新鲜橘子邻居后,放回,这时候我们执行的是排除邻居为烂橘子的情况,就是说你找到邻居是烂橘子,是直接continue跳过的,也就是原来起始列表中的烂橘子,你放回的邻居永远不会和它重复。然后队列里你都执行完以后,再执行起始的第2个烂橘子,此时除非隔离情况,基本第2个橘子是不用进行任何操作的,因为第一个基本覆盖了。

这题和200. Number of Islands 也不一样。岛屿这道题,BFS循环是紧接在你遍历出第一个坐标之后的,而不是在找到所有坐标后再循环。while是写在遍历二维数组内部的,是因为在找到第一个land以后,要不停的把周围的1全消掉,直到够不到的远处隔离的1为止。所以不用担心邻居放回重复,因为你找到的邻居,放回后,位置都离着你起始队列里第二个1很远,不用担心放回重复。

可是这个二叉树,3,找到9和20邻居后,放回9和20,这时候队列里出现了9,20,9,20这情况,这个怎么解释???

忘解惑!谢谢!
10条回复
热度排序

发表回复