1回答

liuyubobobo

2022-03-24

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

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

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

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

继续加油！：）

0

0