广度优先搜索或深度优先搜索在特定深度找到儿童？

Question

我知道在这里处理广度优先搜索与深度优先搜索有很多问题，但我认为我的情况有点不同。

我有一棵有根树，其中每个节点可能有0,1或2个孩子（期望的数字是1）。鉴于大量n，我想找到一个长度为n树的路径。

看起来很清楚，深度优先应该是最好的方法来做到这一点，但我不太确定。树的宽度非常小，这通常是使用宽度优先搜索的原因。另外，如果我使用深度优先搜索，那么我最终可能会进入一个高度非常接近n但小于n的子树。在这种情况下，我会浪费很多时间遍历树不可能给我答案，我想

Answer 1

1. DFS总是比BFS更有效的为你的目标。因为BFS遍历深度为1的全部节点，则深度为2的所有节点等等，为了找到长度为n的路径，BFS将首先穿过长度为< = n- 1。在绝对最坏的情况下，DFS也会这样做直到找到所需的路径，但在一般情况下，我认为DFS会更有效率。

2. 我知道这并不总是可行的，但是你可以改变你的树实现，使得每个节点将包含它的子树的长度（节点的子节点之间的最大值），它会解决你的问题并且在定期插入\移除等过程中很容易维护。