友情支持

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

支付宝

微信

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

wx jikerizhi

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

Tree Depth First Search，树上的DFS

树形DFS基于深搜（Depth First Search (DFS)）技术来实现树的遍历。

咱们可以用递归（或是显式栈，如果你想用迭代方式的话）来记录遍历过程中访问过的父节点。

该模式的运行方式是从根节点开始，如果该节点不是叶子节点，我们需要干三件事：

  1. 需要区别我们是先处理根节点（pre-order，前序），处理孩子节点之间处理根节点（in-order，中序），还是处理完所有孩子再处理根节点（post-order，后序）。

  2. 递归处理当前节点的左右孩子。

识别树形DFS：

  • 你需要按前中后序的DFS方式遍历树

  • 如果该问题的解一般离叶子节点比较近。

经典题目

  1. 79. Word Search

  2. 94. Binary Tree Inorder Traversal

  3. 98. Validate Binary Search Tree

  4. 99. Recover Binary Search Tree

  5. 100. Same Tree

  6. 101. Symmetric Tree

  7. 104. Maximum Depth of Binary Tree

  8. 110. Balanced Binary Tree

  9. 111. Minimum Depth of Binary Tree

  10. 112. Path Sum

  11. 113. Path Sum II

  12. 114. Flatten Binary Tree to Linked List

  13. 116. Populating Next Right Pointers in Each Node

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

  15. 124. 二叉树中的最大路径和

  16. 129. Sum Root to Leaf Numbers

  17. 130. Surrounded Regions

  18. 133. Clone Graph

  19. 144. Binary Tree Preorder Traversal

  20. 145. Binary Tree Postorder Traversal

  21. [0156-binary-tree-upside-down]

  22. 199. Binary Tree Right Side View

  23. 200. 岛屿数量

  24. 207. 课程表

  25. 210. Course Schedule II

  26. [0211-design-add-and-search-words-data-structure]

  27. 226. Invert Binary Tree

  28. 230. Kth Smallest Element in a BST

  29. 235. Lowest Common Ancestor of a Binary Search Tree

  30. 236. 二叉树的最近公共祖先

  31. [0250-count-univalue-subtrees]

  32. 257. Binary Tree Paths

  33. [0261-graph-valid-tree]

  34. [0269-alien-dictionary]

  35. [0270-closest-binary-search-tree-value]

  36. [0272-closest-binary-search-tree-value-ii]

  37. [0285-inorder-successor-in-bst]

  38. 297. Serialize and Deserialize Binary Tree

  39. [0298-binary-tree-longest-consecutive-sequence]

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

  41. [0310-minimum-height-trees]

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

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

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

  45. [0332-reconstruct-itinerary]

  46. [0333-largest-bst-subtree]

  47. 337. 打家劫舍 III

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

  49. 341. Flatten Nested List Iterator

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

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

  52. [0366-find-leaves-of-binary-tree]

  53. [0385-mini-parser]

  54. [0386-lexicographical-numbers]

  55. [0388-longest-absolute-file-path]

  56. [0399-evaluate-division]

  57. 404. Sum of Left Leaves

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

  59. [0419-battleships-in-a-board]

  60. [0426-convert-binary-search-tree-to-sorted-doubly-linked-list]

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

  62. [0430-flatten-a-multilevel-doubly-linked-list]

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

  64. 437. Path Sum III

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

  66. [0463-island-perimeter]

  67. [0472-concatenated-words]

  68. [0490-the-maze]

  69. [0499-the-maze-iii]

  70. 501. Find Mode in Binary Search Tree

  71. [0505-the-maze-ii]

  72. [0508-most-frequent-subtree-sum]

  73. 513. Find Bottom Left Tree Value

  74. [0514-freedom-trail]

  75. 515. Find Largest Value in Each Tree Row

  76. [0529-minesweeper]

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

  78. [0536-construct-binary-tree-from-string]

  79. 538. Convert BST to Greater Tree

  80. 543. Diameter of Binary Tree

  81. [0545-boundary-of-binary-tree]

  82. 547. 省份数量

  83. [0549-binary-tree-longest-consecutive-sequence-ii]

  84. 559. Maximum Depth of N-ary Tree

  85. [0563-binary-tree-tilt]

  86. [0565-array-nesting]

  87. [0572-subtree-of-another-tree]

  88. [0582-kill-process]

  89. [0589-n-ary-tree-preorder-traversal]

  90. [0590-n-ary-tree-postorder-traversal]

  91. [0606-construct-string-from-binary-tree]

  92. 617. Merge Two Binary Trees

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

  94. 637. Average of Levels in Binary Tree

  95. [0642-design-search-autocomplete-system]

  96. [0652-find-duplicate-subtrees]

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

  98. [0655-print-binary-tree]

  99. 662. 二叉树最大宽度

  100. [0663-equal-tree-partition]

  101. [0666-path-sum-iv]

  102. 669. Trim a Binary Search Tree

  103. [0671-second-minimum-node-in-a-binary-tree]

  104. [0672-bulb-switcher-ii]

  105. [0676-implement-magic-dictionary]

  106. [0684-redundant-connection]

  107. [0685-redundant-connection-ii]

  108. [0687-longest-univalue-path]

  109. [0690-employee-importance]

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

  111. 695. Max Area of Island

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

  113. 721. 账户合并

  114. [0733-flood-fill]

  115. [0737-sentence-similarity-ii]

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

  117. [0743-network-delay-time]

  118. [0749-contain-virus]

  119. [0753-cracking-the-safe]

  120. [0756-pyramid-transition-matrix]

  121. [0765-couples-holding-hands]

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

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

  124. [0785-is-graph-bipartite]

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

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

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

  128. [0814-binary-tree-pruning]

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

  130. [0834-sum-of-distances-in-tree]

  131. [0839-similar-string-groups]

  132. [0841-keys-and-rooms]

  133. [0851-loud-and-rich]

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

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

  136. [0872-leaf-similar-trees]

  137. [0886-possible-bipartition]

  138. [0897-increasing-order-search-tree]

  139. [0924-minimize-malware-spread]

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

  141. [0934-shortest-bridge]

  142. [0938-range-sum-of-bst]

  143. [0947-most-stones-removed-with-same-row-or-column]

  144. [0951-flip-equivalent-binary-trees]

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

  146. [0965-univalued-binary-tree]

  147. [0968-binary-tree-cameras]

  148. [0971-flip-binary-tree-to-match-preorder-traversal]

  149. [0979-distribute-coins-in-binary-tree]

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

  151. [0988-smallest-string-starting-from-leaf]

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

  153. [1020-number-of-enclaves]

  154. [1022-sum-of-root-to-leaf-binary-numbers]

  155. [1026-maximum-difference-between-node-and-ancestor]

  156. [1028-recover-a-tree-from-preorder-traversal]

  157. [1034-coloring-a-border]

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

  159. [1038-binary-search-tree-to-greater-sum-tree]

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

  161. [1080-insufficient-nodes-in-root-to-leaf-paths]

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

  163. 1110. Delete Nodes And Return Forest

  164. [1120-maximum-average-subtree]

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

  166. [1145-binary-tree-coloring-game]

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

  168. [1192-critical-connections-in-a-network]

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

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

  171. [1214-two-sum-bsts]

  172. [1233-remove-sub-folders-from-the-filesystem]

  173. [1236-web-crawler]

  174. [1242-web-crawler-multithreaded]

  175. [1245-tree-diameter]

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

  177. [1257-smallest-common-region]

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

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

  180. [1273-delete-tree-nodes]

  181. [1302-deepest-leaves-sum]

  182. [1305-all-elements-in-two-binary-search-trees]

  183. [1306-jump-game-iii]

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

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

  186. [1325-delete-leaves-with-a-given-value]

  187. [1339-maximum-product-of-splitted-binary-tree]

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

  189. [1367-linked-list-in-binary-tree]

  190. [1372-longest-zigzag-path-in-a-binary-tree]

  191. [1373-maximum-sum-bst-in-binary-tree]

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

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

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

  195. [1382-balance-a-binary-search-tree]

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

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

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

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

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

  201. [1462-course-schedule-iv]

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

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

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

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

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

  207. [1506-find-root-of-n-ary-tree]

  208. [1516-move-sub-tree-of-n-ary-tree]

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

  210. [1522-diameter-of-n-ary-tree]

  211. [1530-number-of-good-leaf-nodes-pairs]

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

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

  214. [1600-throne-inheritance]

  215. [1612-check-if-two-expression-trees-are-equivalent]

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

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

  218. 1644. Lowest Common Ancestor of a Binary Tree II

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

  220. [1666-change-the-root-of-a-binary-tree]

  221. [1676-lowest-common-ancestor-of-a-binary-tree-iv]

  222. [1722-minimize-hamming-distance-after-swap-operations]

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

  224. [1743-restore-the-array-from-adjacent-pairs]

  225. [1766-tree-of-coprimes]

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

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

  228. [1820-maximum-number-of-accepted-invitations]

  229. [1858-longest-word-with-all-prefixes]

  230. 1905. Count Sub Islands

  231. [1932-merge-bsts-to-create-single-bst]

  232. [1938-maximum-genetic-difference-query]

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

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

  235. [1973-count-nodes-equal-to-sum-of-descendants]

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

  237. [1993-operations-on-tree]

  238. [2003-smallest-missing-genetic-value-in-each-subtree]

  239. [2049-count-nodes-with-the-highest-score]

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

  241. [2096-step-by-step-directions-from-a-binary-tree-node-to-another]

  242. [2097-valid-arrangement-of-pairs]

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

  244. [2127-maximum-employees-to-be-invited-to-a-meeting]

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

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

  247. [2246-longest-path-with-different-adjacent-characters]

  248. [2265-count-nodes-equal-to-average-of-subtree]

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

  250. [2307-check-for-contradictions-in-equations]

  251. [2313-minimum-flips-in-binary-tree-to-get-result]

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

  253. [2322-minimum-score-after-removals-on-a-tree]

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

  255. [2331-evaluate-boolean-binary-tree]

  256. [2359-find-closest-node-to-given-two-nodes]

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

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

  259. [2378-choose-edges-to-maximize-score-in-a-tree]

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

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

  262. [2440-create-components-with-same-value]

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

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

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

  266. [2476-closest-nodes-queries-in-a-binary-search-tree]

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

  268. [2479-maximum-xor-of-two-non-overlapping-subtrees]

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

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

  271. [2538-difference-between-maximum-and-minimum-price-sum]

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

  273. [2581-count-number-of-possible-root-nodes]

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

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

  276. [2646-minimize-the-total-price-of-the-trips]

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

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

  279. [2689-extract-kth-character-from-the-rope-tree]

  280. [2764-is-array-a-preorder-of-some-binary-tree]

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

  282. [2791-count-paths-that-can-form-a-palindrome-in-a-tree]

  283. [2792-count-nodes-that-are-great-enough]

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

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

  286. [2867-count-valid-paths-in-a-tree]

  287. [2872-maximum-number-of-k-divisible-components]

  288. [2920-maximum-points-after-collecting-coins-from-all-nodes]

  289. [2925-maximum-score-after-applying-operations-on-a-tree]

  290. [2973-find-number-of-coins-to-place-in-tree-nodes]

  291. [3004-maximum-subtree-of-the-same-color]

  292. [3067-count-pairs-of-connectable-servers-in-a-weighted-tree-network]

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

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

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

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

  297. [3241-time-taken-to-mark-all-nodes]

  298. [3249-count-the-number-of-good-nodes]

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

  300. [3313-find-the-last-marked-nodes-in-tree]

  301. [3319-k-th-largest-perfect-subtree-size-in-binary-tree]

  302. [3327-check-if-dfs-strings-are-palindromes]

  303. [3331-find-subtree-sizes-after-changes]

  304. [3367-maximize-sum-of-weights-after-edge-removals]

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

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

  307. [3376-minimum-time-to-break-locks-i]

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

  309. [3385-minimum-time-to-break-locks-ii]

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

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

  312. [3425-longest-special-path]

  313. [3481-apply-substitutions]

  314. [3486-longest-special-path-ii]

  315. [3493-properties-graph]

← Previous: Breadth First Search 广度优先搜索 | ↑ Up: LeetCode 解题笔记 | Next: Trie 前缀树 →