我知道这里有很多关于广度优先搜索和深度优先搜索的问题，但我认为我的情况有点不同 .
我有一个有根的树，其中每个节点可能有0,1或2个子节点（预期数量为1） . 给定一个大数 n ，我想找到一条长度为 n 的树的路径 .
很明显，深度优先应该是最好的方法，但我不太确定 . 树的宽度非常小，这通常是使用广度优先搜索的原因 . 另外，如果我使用深度优先搜索，那么我最终可能会进入一个高度非常接近 n 但小于 n 的子树 . 在这种情况下，我将浪费大量时间穿越一棵树，这棵树不可能给我我想要的答案
1 回答
DFS总是比BFS更有效率 . 由于BFS迭代深度为1的所有节点，然后深度为2的所有节点，依此类推，为了找到长度为n的路径，BFS将首先遍历长度为<= n-1的树中的所有路径 . 在绝对最坏的情况下，DFS会一直这样做，直到找到所请求的路径，但在一般情况下，DFS在我看来会更有效率 .
我知道这并不总是可行的，但是你可以改变你的树实现，这样每个节点都会包含它的子树的长度（节点的子节点之间的最大值），它将解决你的问题并且很容易在常规插入\删除等期间保持