廣度優先搜索或深度優先搜索在特定深度找到兒童？

Question

我知道在這裏處理廣度優先搜索與深度優先搜索有很多問題，但我認爲我的情況有點不同。

我有一棵有根樹，其中每個節點可能有0,1或2個孩子（期望的數字是1）。鑑於大量n，我想找到一個長度爲n樹的路徑。

看起來很清楚，深度優先應該是最好的方法來做到這一點，但我不太確定。樹的寬度非常小，這通常是使用寬度優先搜索的原因。另外，如果我使用深度優先搜索，那麼我最終可能會進入一個高度非常接近n但小於n的子樹。在這種情況下，我會浪費很多時間遍歷樹不可能給我答案，我想

Answer 1

1. DFS總是比BFS更有效的爲你的目標。因爲BFS遍歷深度爲1的全部節點，則深度爲2的所有節點等等，爲了找到長度爲n的路徑，BFS將首先穿過長度爲< = n- 1。在絕對最壞的情況下，DFS也會這樣做直到找到所需的路徑，但在一般情況下，我認爲DFS會更有效率。

2. 我知道這並不總是可行的，但是你可以改變你的樹實現，使得每個節點將包含它的子樹的長度（節點的子節點之間的最大值），它會解決你的問題並且在定期插入\移除等過程中很容易維護。