广度优先遍历,也叫层次遍历。
遍历树结构的方式如图,从根节点开始一层一层遍历,最后输出的结果会是这样 [ A B C D E F G H I J K ]
看似非常简单,但是在实现的时候还是有许多非常值得思考的地方,比如我遍历到了F是我该返回到B,再返回A再去遍历G吗?
但实际上有更优秀的解决办法可以来实现这个问题。
解决思路:
我们可以使用队列结构来解决这个问题,下面的队列将用Q来表示
步骤:
1. 将A加入进 队列 Q中 => [ A ]
2. 然后我们将 A 取出, 取出的同时,将它的孩子节点加入 => [ B C D]
3. 然后我们继续出队 B, 在B出队的时候,我们将 B的子节点入队 => [ C D E F]
4. 出队C, 加入C的子节点 (C 无子节点),所以 => [ D E F]
5. 出队 D,加入D 的子节点 => [ E F G H]
6. 出队 E, 加入E 的子节点 => [ F G H ]
7. 出队 F, 加入F 的子节点 => [ G H I J ]
8. 出队 G, 加入G 的子节点 => [ H I J K ]
9. 继续执行上述步骤,并且每次出队的元素都加入一个结果 array中,当队列Q 被取空的时候,我们就能获得 [ A B C D E F G H I J K ]。
时间复杂度: O(v + e)
v 代表的是书结构中的每一个节点,遍历需要遍历每一个节点,所以时间复杂度是O(v)。e 代表 节点与节点之间的连接,即一个节点有多少个孩子节点,因为我们在遍历每一个节点的同时,需要将每一个节点的孩子节点,加入进我们的queue中,所以时间复杂度是O(e), 因此总体的时间复杂度是O( v + e)
空间复杂度:O(v)
1. 将每一个元素加入进了结果array中。
2. 另外一种情况是只有一个root节点,子节点全都在这个root节点下面,所以queue会存放v个节点 - 1, 1表示root节点
代码实现:
无注释版本
Reference:代码来自Algoexpert,以学习作为主要目的来分享的。