递归与DFS

Question

bobo老师。您在这节课里说，很多算法都只是修改DFS的框架，比如添加参数、修改返回值。我突然想到，前几天在学习您在leetcode刷题那门课的第7章，关于树的递归的内容，虽然没有明确提到DFS，但是很多题目都是关于root-to-leaf或者pathSum的问题。我的问题是，这些题目是不是也可以看成是DFS算法的内容？可以通过修改本章的DFS框架来实现呢？谢谢

Answer 1

liuyubobobo 2022-03-24 07:46:59

是的，那些问题都是 dfs 的问题。

你可以把那些问题的代码和这里的图论代码比较一下，他们其实本质是一致的。但是因为结构上的不同（比如树中一个 node 直接用 left 和 right 表示相邻的两个节点，而图中一个 node 的相邻节点是一个列表），所以看起来有差异。但他们本质是一样的。

树的 DFS 和图的 DFS 最大的不同是，图的 DFS 需要一个 visited 数组做标记，以避免重复遍历，而树不需要。因为树中的一个节点不会被重复遍历（想想为什么？）

至于“算法框架”，我个人不建议你去“背”一个“框架”，然后套到相似的问题里做修改得到解决问题的代码。尤其是对于 dfs 这么基础的问题来说。我希望你能更深刻地理解，他们本质都是 dfs，对于 dfs，不管是树的 dfs，还是图的 dfs，应该能完全理解其中过的逻辑过程，根据这个逻辑过程直接写出来，而不是背一个“模板”。问题之间的逻辑联系是需要仔细挖掘的。代码是逻辑的体现，一旦你彻底理解了其中的逻辑，你应该能写出对应的代码。（这本身也是计算机专业的基本要求，即把逻辑用代码表达出来。）

继续加油！：）