529 Minesweeper

輸入：一個二維矩陣，一些修改規則。
　如果點到一個隱藏的地雷M，把它改為X，游戲結束
　如果點到一個E，且其周圍8鄰接的范圍沒有地雷，那么應該把8鄰接的范圍的格子全部翻開為E
　如果翻開的格子的八鄰接范圍有隱藏的地雷，就將其標注了地雷的數目1-8而非E。（規則拷貝鏈接）

輸出：掃雷后的矩陣。
分析：從第二條規則可以看到這是需要迭代遞歸的。遞歸過程可以從一個節點開始，不斷查找鄰接點，擴展下去，也可以沿著節點一層一層擴展下去。前者是DFS，后者是BFS。和前面的幾道題目是一樣的。
這個題目的難點1是英語問題，沒有理解 If an empty square (‘E’) with no adjacent mines is revealed, then change it to revealed blank (‘B’) and all of its adjacent unrevealed squares should be revealed recursively。 難點2 是計算鄰接點坐標變化的change數組。知道8個方向上xy坐標值得變化。
　看代碼會發現，依然使用的是BFS的模板。有了套路真好。有時間再回頭看看DFS的套路。整個做完DFS并沒有目前對BFS的套路感覺。
代碼

102. Binary Tree Level Order Traversal

我認為不值得再寫個新文章。如果從BFS的習題練習到這里，大概已經形成思路。套用即可。最近在用idea寫LeetCode的代碼。我認為idea就是開發工具界的搜狗輸入法。好用，好用，真好用。
代碼

199. Binary Tree Right Side View

輸入：二叉樹
輸出：從右邊站著看二叉樹，從上到下得到的值。
分析：這與102比較，102要求記下一層中的每一個節點的值，199要求記錄下一層中最右邊節點的值。用BFS思路的話，只要把上一題的代碼拷貝過來，改改即可。用DFS思路的話，也是拷貝上一題的代碼，改改就能跑起來。如果能先遍歷左節點，每層只調用一次list的add方法，速度會更快。
代碼

863. All Nodes Distance K in Binary Tree

輸入：二叉樹，目標節點，距離K
輸出：所有距離目標節點距離K路徑的節點值列表
思路1：

首先找到根節點距離target node 的距離 rootDistance；
其次，存儲所有節點與父節點的map
最后，一個節點距離目標節點的距離t = 其父節點距離目標的節點 + 1
假設dist[i] 表示值為i的節點距離目標節點的距離。dist[3]=1,dist[5]=0,dist[1]=dist[3]+1,dist[2]=dist[5]+1。考慮到這里，我就認為dist[node]=dist[node.parent]+1.假設在node3和node5之間加一個節點node9，實際dist[9]=1，按照公式dist[9]=dist[3]+1.不正確。
這種通過一兩個節點（特例）來總結規律的情況，需要考慮全所有的情況。

糾正思路1：
1 樹的遍歷不一定非要從跟節點開始。
2 直觀地看。如果target 在一個節點的左子樹，距離為dist，則這個節點的右子樹上距離為K-dist的節點都符合要求。當然，target節點子樹上再遍歷K層的元素也符合要求。例如目標節點是6，K=2。節點5與節點6距離為1，那么節點5的右子樹上，與節點5距離為K-1=1的節點符合要求。節點6距離節點3的距離為2，節點3符合要求。當然對于節點6的子節點，距離為K的子節點也符合要求。
3 如果 target在右子樹上，情形也是一樣的。
這道題目最好不要看做樹，而是看做圖。因為當看做樹的時候會更多的去考慮父子關系和父子節點。如果看做圖，則所有節點地位相同。
代碼方法：distanceKV2

思路2：
1 存儲所有節點與父節點的map。
2 將node5加入到隊列。dist=0。
3如果dist<K, 彈出隊列所有元素，將每個元素的子節點，父節點加入到隊列。dist++。調回2。
4如果dist=K，彈出隊列所有元素，將元素值放入list中，作為結果集。
做的過程中會發現有重復處理的元素，不合理的結果。這時候用一個set，在加入到隊列之前，判斷一下是否已經處理過。
代碼方法：distanceK
代碼

總結

以上是生活随笔為你收集整理的【Breadth-first Search 】专题3的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。