需要每一道DFS都需要掌握Rec和Iter两种写法吗？

有的题目DFS（Rec + Iter）都能做。

面试中比如说有Rec的思路，写完了面试官会要求你用Iter再写一遍吗？

有的题目是天生适合Iter写法的，那种当然要最优解用Iter。如果Rec和Iter平行，那么面试官会要求你两个都写一遍吗？

我通常都会先写rec，然后如果加码要求iter的话我就说个思路，跟面试官说要真的实现出来会比较费劲。
除非是面google或者问的是fibonacci这种复杂度明显不同的问题，否则我不觉得需要熟练地掌握两种不同方法。特别是tree traversal这种问题，recurse的复杂度已经很清楚也很低了。
而dfs的iter写法也就那么一回事，我觉得能懂原理就行了。

DFS用rec的话要小心堆栈溢出

小亩_p2pi9i9 发表于 2022-6-4 00:26
我通常都会先写rec，然后如果加码要求iter的话我就说个思路，跟面试官说要真的实现出来会比较费劲。
除非是 ...

好的，谢谢。比如有的题目DFS拓扑排序和DFS都能做，因为我拓扑排序比DFS要熟练，如果面试碰到了，我写完拓扑排序，应该就不会再要求我写一遍DFS吧？我看有的说用DP写了一遍，面试官问能不能用DFS写，这个可以理解。我整体BFS比DFS熟练，对于一些两种解法平行的题目，比如矩阵类的，面试用最熟的写出来应该就ok了吧？主要就是感觉如果一道题都准备3，4个解法，那感觉刷200道相当于刷600道，量太大了