关于BFS创建队列后，放入元素问题。。。。。。。。。。。。。

我知道在执行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这情况，这个怎么解释？？？

忘解惑！谢谢！

thrillerの空 发表于 2021-07-20 18:32:46
题主最主要的问题就是认为append（入队）一个TreeNode会把所有相关的Node都入队，这样是不对的额，每次append只会入队一个Node的指针，所以不会出现“此时我们首先是把root全部放入

好的，很多新知识，我得好好消化一下您写的，万分感谢！

题主最主要的问题就是认为append（入队）一个TreeNode会把所有相关的Node都入队，这样是不对的额，每次append只会入队一个Node的指针，所以不会出现“此时我们首先是把root全部放入队列，这时候root里 root = [3,9,20,null,null,15,7] 这些数据可是全进队列了。”这种情况。
我画了一个BFS的例子，列出了每次循环queue的状态，题主可以自己理解一下，而且如果有用IDE，可以用degguer看看每入队一次，queue的状态，这样可以清晰的看到queue里面的所有元素：

另外，BFS会把遍历的图按照访问先后的层级顺序将node排序，题主有兴趣可以看看下面的图片：

看到这里，BFS求最短路径问题就很简单了，但BFS求最短路径需要有一个条件：所有边的权重必须相同，否则BFS算出来的路径不一定是最短的，需要用到其他最短路径算法，比如Dijkstra或Bellman Ford。比如下面这个图就描述上面图例从 0 -> 8的最短路径：

不是你add root就只是root咋还能把那一列全放进去了呢。。
add 每一个node就只加那个node本身 不会加一串

楼主对Binary Tree 的 TreeNode 理解可能还需要加深一下
“我们要执行queue.append(root)。此时我们首先是把root全部放入队列，这时候root里 root = [3,9,20,null,null,15,7] 这些数据可是全进队列了。“
这句话有点问题，这个时候queue里面只有root一个元素，只是TreeNode自身有属性left，right 分别指向值为9， 20 左右子树而已。
你可以试一下queue.append(root) -> len(queue)就会明白了

溜溜 发表于 2021-7-21 01:59
不是你add root就只是root咋还能把那一列全放进去了呢。。
add 每一个node就只加那个node本身 不会加一串

谢谢！我仔细再补补基础，零基础总范低级错误

Maxtk7xox 发表于 2021-7-21 02:03
楼主对Binary Tree 的 TreeNode 理解可能还需要加深一下
“我们要执行queue.append(root)。此时我们首先是 ...

谢谢，很详细！清楚了！我还得补补基础多，有问题再问您！

ATPtennis 发表于 2021-7-20 17:41
谢谢，很详细！清楚了！我还得补补基础多，有问题再问您！

嗯嗯，可以去补一下Binary Tree这个结构 linked list里的 ListNode 其实也是这样 每一个ListNode 仅代表自己这一个元素，这个元素的attributes又有val 和next. next指向下一个节点（存的也是下一个node的索引）

单词接龙2真的难

我一般不用queue，直接手动遍历每层。

1. thisLevel = []seen = set()
   
2. while thisLevel:
   
3.   nextLevel = []
   
4.   for node in thisLevel:
   
5.     if node in seen:
   
6.       continue
   
7.     seen.add(node)
   
8.     for nextNode in node.neighbors:
   
9.       nextLevel.append(nextNode)
   
10.   thisLevel = nextLevel
    
11.   

复制代码

Maxtk7xox 发表于 2021-07-20 18:16:50
嗯嗯，可以去补一下Binary Tree这个结构 linked list里的 ListNode 其实也是这样 每一个ListNode 仅代表自己这一个元素，这个元素的attributes又有val 和

好的，就按您这个索引去看，真的是太感谢了！困惑了很久