如何在BFS中遍历时存储每个节点的级别？

Question

如果我们有一个二叉树：

      7
    /  \
   5    6
  /\    /\
 2  3   1 4
   /
  5

如何打印以下输出？

[7],
[5,6]
[2,3,1,4]
[5]

意味着执行BFS并将每个级别的节点存储在列表中，然后打印列表？

我能够在BFS中遍历，但无法找到树中每个元素的正确级别。

如何找到每个节点的正确级别并使用其级别值丰富节点对象？

这是我的逻辑：

1. BFS中的遍历
2. 使用其级别值丰富树的每个节点。
3. 在列表中存储节点
4. 遍历列表并创建<Level,List<Node>>地图
5. 将节点级别存储在Set<Integer>中，然后转换为列表和排序。
6. 遍历新创建的级别列表，并从地图中找到该列表上的适当节点并打印出来。

Answer 1

树的遍历将是：

7-5-7 -6 -7-5-2-5-3-5-5-5-7-6-1-6-4

逻辑是。

如果你不能选择一个左撇子，总是选择一个左孩子，如果你不能选择任何一个孩子，选择一个右孩子，去找父母

在打印方面，跟踪访问过的节点，如果访问过它们，就不要打印它们，这样就不会打印“回溯”。

您的节点(在伪代码中)应该如下所示：

Node {
   Node *parent;
   Node *child_left;
   Node *child_right;
   Boolean visited;
   int level;
}

每个节点应该有一个父节点(根节点除外)，并且可以选择有子节点。一旦您遍历它，就会将访问设置为true。

当您下降一个级别(即访问一个子级别)时，您应该增加一个global_level变量。当你回去的时候(即拜访父母)，你应该减少它。

要将它们存储在一个列表中，您只需要拥有一个全局列表，只是如果已经访问过它，就不要按它。

Answer 2

使用BFS进行遍历。

有两个计数-一个是当前级别中的节点数量(从1开始)，另一个是保留在下一个级别上的节点数(从0开始)。

每当处理节点时，减少当前级别计数，并增加添加到队列中的每个子节点的下一个级别计数。

如果当前级别计数达到0，则启动一个新列表。将当前级别计数设置为下一个级别计数，并将当前级别计数设置为0。

以树为例：

Current level count = 1
Next level count = 0

Queue: 7
Dequeue 7, enqueue 5 and 6.

Current list: [7]

Current level count = 1 - 1 = 0
Next level count = 0 + 2 = 2

Current level count == 0, so
Current level count = Next level count = 2
Next level count = 0

Finished with [7], starting a new list


Queue: 5, 6
Dequeue 5, enqueue 2 and 3.

Current list: [5]

Current level count = 2 - 1 = 1
Next level count = 0 + 2 = 2


Queue: 6, 2, 3
Dequeue 6, enqueue 1 and 4.

Current list: [5, 6]
...

Answer 3

假设树中的所有节点都从1到n，我们可以使用两个数组来存储节点的级别。

int [] parent = new int[n + 1];//To store the direct parent of the current node
int [] level = new int[n + 1];//To store the level of the current node

从根的0级开始，索引7将具有值level[7] = 0；它的两个子级5和6将具有parent[5] = 7 and parent[6] = 7；类似地，level[5] = level[parent[5]] + 1和level[6] = level[parent[6]] + 1。

通过这些步骤，您可以通过通过BFS填充parent和level数组来逐步构建树结构。

伪码

int [] parent = new int[n + 1];
int [] level = new int[n + 1];
Queue q = new Queue();
level[root.index] = 0;
q.add(root);
while(!q.isEmpty()){
    Node node = q.dequeue();
    parent[node.left.index] = node.index;
    parent[node.right.index] = node.index;
    level[node.left.index] = level[parent[node.left.index]] + 1;
    level[node.right.index] = level[parent[node.right.index]] + 1;
    q.add(node.left);
    q.add(node.right);

}