查找給定節點級別的所有節點

Question

這是一個採訪問題： 給定二叉樹的節點'k'，找到它的所有兄弟和表兄弟。沒有可用於節點的nextPointer。

考辛斯：在相同的水平給定節點「K」排除「K」

的兄弟我知道答案，可以找到的水平，在其中，k謊言（第1次），然後打印所有節點該級別的節點（第2遍）（使用級別遍歷）。但是，這將是一個2遍算法。任何人都可以爲它提出一個通過或更有效的算法。

實施例：

 15 
    /\ 
    18 19 
/\ /\ 
    2 3 4 5 
/\//\ 
1 6 7 8 9 

Input: k=6 
Output: 1,7,8,9 

Answer 1

的算法的概要是使用改性BFS：

1. 設置一個隊列爲空
2. 設置一個布爾 '發現' 爲假。
3. 排隊根。
4. 入隊一個空佔位符。
5. 對於隊列中的每個元素，直到佔位符排入子元素。排隊時，如果數字與輸入值匹配，則將'found'設置爲true。
6. 將空佔位符從前面移到隊列後面。
7. 如果發現是錯誤，則繼續5.
8. 如果找到是true，則打印排除該值的隊列。

這將在一次通過。

Answer 2

使用BFS以級別順序打印樹，然後使用給定節點檢查每個級別。時間複雜度是O（n）。