查找给定节点级别的所有节点

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）。