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

Question

这是一个面试题:给定二叉树的节点“k”，找到它的所有 sibling 和堂 sibling 。没有可用于节点的 nextPointer。

Cousins:与给定节点“k”处于同一级别的节点，不包括“k”的兄弟节点

我知道答案可能是找到 k 所在的级别(第一遍)，然后打印该级别的所有节点(第二遍)(通过使用级别顺序遍历)。然而，这将是一个 2-pass 算法。任何人都可以为它提出一个一次性或更有效的算法。

示例:

      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. 将 bool 值“found”设置为 false。
3. 对根进行排队。
4. 排队空占位符。
5. 对于占位符之前队列中的每个元素，将其子元素加入队列。入队时，如果数字与输入值匹配，则将“found”设置为 true。
6. 将 null 占位符从队列的前面移到后面。
7. 如果发现是假的继续5。
8. 如果发现为真，则打印排除该值的队列。

这将一次性完成。