我该如何存储每个节点的水平，同时遍历BFS？ [英] How do I store level of each node while traversing in BFS?

问题描述

如果我们有一个二叉树：

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

我怎样才能打印输出以下？

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

意味着你要做一个BFS和存储节点在列表中的每个级别，然后打印清单？

我能够在BFS遍历，但我无法找到树中的每个元素的适当水平。

我怎样才能找到每个节点的正确的水平和丰富的节点对象，其电平值？

这是我的逻辑：

1. 导线在BFS

2. 充实树的每个节点的电平值

3. 在列表中存储节点

4. 遍历列表，并创建一个地图＆LT;等级，列表和LT;节点＆GT;＆GT;

5. 存储在节点A级设置＆LT;整数GT; ，然后转换成列和排序

6. 循环访问级别的新创建的列表，找到从图，表上的相应节点，并打印

解决方案

下面是一个办法做到这一点而不做任何更改到树节点结构或任何其他的事情。

1. 请在 levelcounter = 0 的现有水平，而阅读BFS队列

2. 还留着nextlevel指针节点是第一个在队列中的一个新的水平。

3. Inital nextlevel = NULL 。

4. 在新的孩子加入到排队检查，如果nextlevel指针不为空，如果空然后将其设置为当前子节点指针。

5. 如果nextlevel等于指针最近删除的子然后增加levelcounter并设置 nextlevel = NULL

按 levelcounter 指示的水平是在树中的结点的水平。

If we have a binary tree:

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

How can I print the below output?

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

Means doing a BFS and storing nodes at each level in a list and then printing the list?

I am able to traverse in BFS, but I am not able to find correct level of each element in the tree.

How can I find correct level of each node and enrich the node object with its level value?

This is my logic:

1. Traverse in BFS

2. Enrich each node of the tree with its level value

3. Store node in the list

4. Traverse the list and create a Map of <Level,List<Node>>

5. Store the nodes level in a Set<Integer> and then convert to list and sort it.

6. Iterate through the newly created List of level and find the appropriate node on that list from map and print it

解决方案

Here is a way to do it without making any changes to the tree node structure or any thing else.

1. Keep a levelcounter = 0 of current level while reading the BFS queue

2. Also keep the nextlevel pointer to node which is first in the next level in the queue.

3. Inital nextlevel = null.

4. When new child is added to queue check if nextlevel pointer is not null , if null then set it to current child node pointer.

5. If nextlevel is equal to pointer of recently deleted child then increment levelcounter and set nextlevel = null

The level indicated by levelcounter is your nodes level in tree.

这篇关于我该如何存储每个节点的水平，同时遍历BFS？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！