友情支持

如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜

支付宝

微信

有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

Tree Breadth First Search，树上的BFS

这种模式基于宽搜（Breadth First Search (BFS)），适用于需要遍历一颗树。借助于队列数据结构，从而能保证树的节点按照他们的层数打印出来。打印完当前层所有元素，才能执行到下一层。所有这种需要遍历树且需要一层一层遍历的问题，都能用这种模式高效解决。

这种树上的BFS模式是通过把根节点加到队列中，然后不断遍历直到队列为空。每一次循环中，我们都会把队头结点拿出来（remove），然后对其进行必要的操作。在删除每个节点的同时，其孩子节点，都会被加到队列中。

识别树上的BFS模式：

  • 如果你被问到去遍历树，需要按层操作的方式（也称作层序遍历）

经典题目

  1. 100. Same Tree

  2. 101. Symmetric Tree

  3. 102. 二叉树的层序遍历

  4. 103. Binary Tree Zigzag Level Order Traversal

  5. 104. Maximum Depth of Binary Tree

  6. 107. Binary Tree Level Order Traversal II

  7. 111. Minimum Depth of Binary Tree

  8. 112. Path Sum

  9. 116. Populating Next Right Pointers in Each Node

  10. 117. Populating Next Right Pointers in Each Node II

  11. [0126-word-ladder-ii]

  12. 127. Word Ladder

  13. 130. Surrounded Regions

  14. 133. Clone Graph

  15. 199. Binary Tree Right Side View

  16. 200. 岛屿数量

  17. 207. 课程表

  18. 210. Course Schedule II

  19. 226. Invert Binary Tree

  20. [0261-graph-valid-tree]

  21. [0269-alien-dictionary]

  22. 279. Perfect Squares

  23. [0286-walls-and-gates]

  24. 297. Serialize and Deserialize Binary Tree

  25. [0301-remove-invalid-parentheses]

  26. [0302-smallest-rectangle-enclosing-black-pixels]

  27. [0310-minimum-height-trees]

  28. [0314-binary-tree-vertical-order-traversal]

  29. [0317-shortest-distance-from-all-buildings]

  30. 322. 零钱兑换

  31. [0323-number-of-connected-components-in-an-undirected-graph]

  32. [0329-longest-increasing-path-in-a-matrix]

  33. [0339-nested-list-weight-sum]

  34. [0364-nested-list-weight-sum-ii]

  35. [0365-water-and-jug-problem]

  36. [0399-evaluate-division]

  37. 404. Sum of Left Leaves

  38. [0407-trapping-rain-water-ii]

  39. [0417-pacific-atlantic-water-flow]

  40. [0428-serialize-and-deserialize-n-ary-tree]

  41. 429. N-ary Tree Level Order Traversal

  42. [0431-encode-n-ary-tree-to-binary-tree]

  43. [0433-minimum-genetic-mutation]

  44. [0449-serialize-and-deserialize-bst]

  45. [0463-island-perimeter]

  46. [0488-zuma-game]

  47. [0490-the-maze]

  48. [0499-the-maze-iii]

  49. [0505-the-maze-ii]

  50. 513. Find Bottom Left Tree Value

  51. [0514-freedom-trail]

  52. 515. Find Largest Value in Each Tree Row

  53. [0529-minesweeper]

  54. 530. 二叉搜索树的最小绝对差

  55. [0542-01-matrix]

  56. 547. 省份数量

  57. 559. Maximum Depth of N-ary Tree

  58. [0582-kill-process]

  59. 617. Merge Two Binary Trees

  60. [0623-add-one-row-to-tree]

  61. 637. Average of Levels in Binary Tree

  62. [0653-two-sum-iv-input-is-a-bst]

  63. [0655-print-binary-tree]

  64. 662. 二叉树最大宽度

  65. [0672-bulb-switcher-ii]

  66. [0675-cut-off-trees-for-golf-event]

  67. [0684-redundant-connection]

  68. [0685-redundant-connection-ii]

  69. [0690-employee-importance]

  70. [0694-number-of-distinct-islands]

  71. 695. Max Area of Island

  72. [0711-number-of-distinct-islands-ii]

  73. 721. 账户合并

  74. [0733-flood-fill]

  75. [0737-sentence-similarity-ii]

  76. [0742-closest-leaf-in-a-binary-tree]

  77. [0743-network-delay-time]

  78. [0749-contain-virus]

  79. 752. Open the Lock

  80. [0756-pyramid-transition-matrix]

  81. [0765-couples-holding-hands]

  82. [0773-sliding-puzzle]

  83. [0778-swim-in-rising-water]

  84. [0783-minimum-distance-between-bst-nodes]

  85. [0785-is-graph-bipartite]

  86. [0787-cheapest-flights-within-k-stops]

  87. [0797-all-paths-from-source-to-target]

  88. [0802-find-eventual-safe-states]

  89. [0815-bus-routes]

  90. [0827-making-a-large-island]

  91. [0839-similar-string-groups]

  92. [0841-keys-and-rooms]

  93. [0847-shortest-path-visiting-all-nodes]

  94. [0854-k-similar-strings]

  95. [0863-all-nodes-distance-k-in-binary-tree]

  96. [0864-shortest-path-to-get-all-keys]

  97. [0865-smallest-subtree-with-all-the-deepest-nodes]

  98. [0886-possible-bipartition]

  99. [0909-snakes-and-ladders]

  100. [0919-complete-binary-tree-inserter]

  101. [0924-minimize-malware-spread]

  102. [0928-minimize-malware-spread-ii]

  103. [0934-shortest-bridge]

  104. [0958-check-completeness-of-a-binary-tree]

  105. [0959-regions-cut-by-slashes]

  106. [0965-univalued-binary-tree]

  107. [0967-numbers-with-same-consecutive-differences]

  108. [0987-vertical-order-traversal-of-a-binary-tree]

  109. [0993-cousins-in-binary-tree]

  110. [0994-rotting-oranges]

  111. [1020-number-of-enclaves]

  112. [1034-coloring-a-border]

  113. [1036-escape-a-large-maze]

  114. [1042-flower-planting-with-no-adjacent]

  115. [1087-brace-expansion]

  116. [1091-shortest-path-in-binary-matrix]

  117. [1096-brace-expansion-ii]

  118. [1102-path-with-maximum-minimum-value]

  119. [1123-lowest-common-ancestor-of-deepest-leaves]

  120. [1129-shortest-path-with-alternating-colors]

  121. [1161-maximum-level-sum-of-a-binary-tree]

  122. [1162-as-far-from-land-as-possible]

  123. [1197-minimum-knight-moves]

  124. [1202-smallest-string-with-swaps]

  125. [1203-sort-items-by-groups-respecting-dependencies]

  126. [1210-minimum-moves-to-reach-target-with-rotations]

  127. [1215-stepping-numbers]

  128. [1236-web-crawler]

  129. [1242-web-crawler-multithreaded]

  130. [1245-tree-diameter]

  131. [1254-number-of-closed-islands]

  132. [1257-smallest-common-region]

  133. [1261-find-elements-in-a-contaminated-binary-tree]

  134. [1263-minimum-moves-to-move-a-box-to-their-target-location]

  135. [1267-count-servers-that-communicate]

  136. [1273-delete-tree-nodes]

  137. [1284-minimum-number-of-flips-to-convert-binary-matrix-to-zero-matrix]

  138. [1293-shortest-path-in-a-grid-with-obstacles-elimination]

  139. [1298-maximum-candies-you-can-get-from-boxes]

  140. [1302-deepest-leaves-sum]

  141. [1306-jump-game-iii]

  142. [1311-get-watched-videos-by-your-friends]

  143. [1315-sum-of-nodes-with-even-valued-grandparent]

  144. [1319-number-of-operations-to-make-network-connected]

  145. [1345-jump-game-iv]

  146. [1361-validate-binary-tree-nodes]

  147. [1368-minimum-cost-to-make-at-least-one-valid-path-in-a-grid]

  148. [1376-time-needed-to-inform-all-employees]

  149. [1377-frog-position-after-t-seconds]

  150. [1379-find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree]

  151. [1391-check-if-there-is-a-valid-path-in-a-grid]

  152. [1430-check-if-a-string-is-a-valid-sequence-from-root-to-leaves-path-in-a-binary-tree]

  153. [1443-minimum-time-to-collect-all-apples-in-a-tree]

  154. [1448-count-good-nodes-in-binary-tree]

  155. [1457-pseudo-palindromic-paths-in-a-binary-tree]

  156. [1462-course-schedule-iv]

  157. [1466-reorder-routes-to-make-all-paths-lead-to-the-city-zero]

  158. [1469-find-all-the-lonely-nodes]

  159. [1483-kth-ancestor-of-a-tree-node]

  160. [1485-clone-binary-tree-with-random-pointer]

  161. [1490-clone-n-ary-tree]

  162. [1519-number-of-nodes-in-the-sub-tree-with-the-same-label]

  163. [1559-detect-cycles-in-2d-grid]

  164. [1568-minimum-number-of-days-to-disconnect-island]

  165. [1602-find-nearest-right-node-in-binary-tree]

  166. [1609-even-odd-tree]

  167. [1625-lexicographically-smallest-string-after-applying-operations]

  168. [1631-path-with-minimum-effort]

  169. [1654-minimum-jumps-to-reach-home]

  170. [1660-correct-a-binary-tree]

  171. [1730-shortest-path-to-get-food]

  172. [1740-find-distance-in-a-binary-tree]

  173. [1765-map-of-highest-peak]

  174. [1778-shortest-path-in-a-hidden-grid]

  175. [1810-minimum-path-cost-in-a-hidden-grid]

  176. 1905. Count Sub Islands

  177. [1926-nearest-exit-from-entrance-in-maze]

  178. [1970-last-day-where-you-can-still-cross]

  179. [1971-find-if-path-exists-in-graph]

  180. [1992-find-all-groups-of-farmland]

  181. [1993-operations-on-tree]

  182. [2039-the-time-when-the-network-becomes-idle]

  183. [2045-second-minimum-time-to-reach-destination]

  184. [2059-minimum-operations-to-convert-number]

  185. [2092-find-all-people-with-secret]

  186. [2101-detonate-the-maximum-bombs]

  187. [2146-k-highest-ranked-items-within-a-price-range]

  188. [2174-remove-all-ones-with-row-and-column-flips-ii]

  189. [2192-all-ancestors-of-a-node-in-a-directed-acyclic-graph]

  190. [2204-distance-to-a-cycle-in-undirected-graph]

  191. [2258-escape-the-spreading-fire]

  192. [2277-closest-node-to-path-in-tree]

  193. [2290-minimum-obstacle-removal-to-reach-corner]

  194. [2316-count-unreachable-pairs-of-nodes-in-an-undirected-graph]

  195. [2328-number-of-increasing-paths-in-a-grid]

  196. [2360-longest-cycle-in-a-graph]

  197. [2368-reachable-nodes-with-restrictions]

  198. [2385-amount-of-time-for-binary-tree-to-be-infected]

  199. [2415-reverse-odd-levels-of-binary-tree]

  200. [2445-number-of-nodes-with-value-one]

  201. [2458-height-of-binary-tree-after-subtree-removal-queries]

  202. [2467-most-profitable-path-in-a-tree]

  203. [2471-minimum-number-of-operations-to-sort-a-binary-tree-by-level]

  204. [2477-minimum-fuel-cost-to-report-to-the-capital]

  205. [2492-minimum-score-of-a-path-between-two-cities]

  206. [2493-divide-nodes-into-the-maximum-number-of-groups]

  207. [2503-maximum-number-of-points-from-grid-queries]

  208. [2556-disconnect-path-in-a-binary-matrix-by-at-most-one-flip]

  209. [2577-minimum-time-to-visit-a-cell-in-a-grid]

  210. [2583-kth-largest-sum-in-a-binary-tree]

  211. [2596-check-knight-tour-configuration]

  212. [2608-shortest-cycle-in-a-graph]

  213. [2612-minimum-reverse-operations]

  214. [2617-minimum-number-of-visited-cells-in-a-grid]

  215. [2641-cousins-in-binary-tree-ii]

  216. [2658-maximum-number-of-fish-in-a-grid]

  217. [2685-count-the-number-of-complete-components]

  218. [2773-height-of-special-binary-tree]

  219. [2812-find-the-safest-path-in-a-grid]

  220. [2814-minimum-time-takes-to-reach-destination-without-drowning]

  221. 2850. 将石头分散到网格图的最少移动次数

  222. [2852-sum-of-remoteness-of-all-cells]

  223. [2858-minimum-edge-reversals-so-every-node-is-reachable]

  224. [2998-minimum-number-of-operations-to-make-x-and-y-equal]

  225. [3015-count-the-number-of-houses-at-a-certain-distance-i]

  226. [3123-find-edges-in-shortest-paths]

  227. [3141-maximum-hamming-distances]

  228. [3157-find-the-level-of-tree-with-minimum-sum]

  229. [3203-find-minimum-diameter-after-merging-two-trees]

  230. [3235-check-if-the-rectangle-corner-is-reachable]

  231. [3243-shortest-distance-after-road-addition-queries-i]

  232. [3283-maximum-number-of-moves-to-kill-all-pawns]

  233. [3286-find-a-safe-walk-through-a-grid]

  234. [3310-remove-methods-from-project]

  235. [3372-maximize-the-number-of-target-nodes-after-connecting-trees-i]

  236. [3373-maximize-the-number-of-target-nodes-after-connecting-trees-ii]

  237. [3383-minimum-runes-to-add-to-cast-spell]

  238. [3387-maximize-amount-after-two-days-of-conversions]

  239. [3419-minimize-the-maximum-edge-weight-of-graph]

  240. [3481-apply-substitutions]

  241. [3493-properties-graph]

参考资料

链接中，有双向 BFS 的介绍，可以抽空了解一下。

  1. 752. 打开转盘锁 - 一题三解：「双向 BFS」& 「AStar 算法」&「IDA* 算法」 — 双向 BFS 有点意思。

  2. 752. 打开转盘锁 - 双向BFS详解，两面包夹芝士寻找起点与终点的最短路上的汇集点，妈妈再也不用担心BFS复杂…​

  3. 752. 打开转盘锁 - BFS、双向BFS清晰易懂方法论 [图解] & [框架] & [超详细注释]

← Previous: K-way merge 多路归并 | ↑ Up: LeetCode 解题笔记 | Next: Depth First Search 深度优先搜索 →