【刷题日记】429. N 叉树的层序遍历
本次刷题日记的第 27 篇，力扣题为：429. N 叉树的层序遍历 ，中等
一、题目描述：
今天来的每日一题是树类的题目，一般来说，如果是二叉树的题目，相对来说是比较好理解，比较好做的，虽然看着是一个中等题，其实实现方式比较明确也比较好理解，可能没有练习过二叉树的会感觉到无从下手吧
我们一起来看看吧
二、这道题考察了什么思想？你的思路是什么？
我们仔细看看今日一题给了我们哪些重要的信息：
- 题目中给出的树是多叉树，和二叉树不一样，一个节点最多只会有 2 个孩子节点，一个左孩子，一个右孩子，但是多叉树是可以有多个孩子节点的
- 需要我们对树层序遍历，见名知意，就是一层一层的遍历即可
之前我们刷过二叉树的题目，例如遍历树的前序，后序，中序，还记得我们使用的是递归的方式，是 dfs 深度优先算法
那么这一次的层序遍历，是不是深度优先算法呢？
我们可以来推演一下：
按照题目中的示例：root = [1,null,3,2,4,null,5,6]
主要是我们要看明白下面这个图
遍历这棵树，咱们是一层一层遍历的，先遍历第一层
再遍历第二层，我们知道第二层是第一层的子节点，那么我们在遍历第一层的时候，就可以用一个帮助空间来将第一层的所有子节点的地址先存起来，当遍历第二层的时候就可以用
当遍历第三层的时候，做法也是和遍历第二层的方式一样
那么当第三层遍历完毕的时候，我们发现，第三层的节点中，已经没有哪个节点有孩子节点了，因此，我们则认为是遍历完毕
那么最后，我们将每一层的节点数字，输出出来即可
剩下的就是翻译上述思路的过程了，思路清楚了，写代码那都是 soso 滴
三、编码
根据上述逻辑和分析，我们就可以翻译成如下代码
编码如下：
/** * Definition for a Node. * type Node struct { * Val int * Children []*Node * } */ func levelOrder(root *Node)(res [][]int) { // 如果传入的根节点是 空，那么就不存在层序遍历了 if root == nil{ return } // 定义一个队列，先将根节点放入队头 que := []*Node{root} for que != nil { tmp := que que = nil // 定义一个切片，主要是存放本层的 节点数据 tmpLevel := []int{} for _,val := range tmp { // 存放本层节点数据 tmpLevel = append(tmpLevel, val.Val) // 将当前节点的子节点入队列 que = append(que, val.Children...) } // 将本层节点加入到结果集 res = append(res, tmpLevel) } return }
可以看到节点的结构是这样的
每一个节点都有自己的值域和指针域，指针域存放的是一个切片，里面存放的是自己的多个子节点的地址
那么通过上述编码，我们知道，是将这棵树的每一个节点，按照一层一层的将节点放入队列中，先进先出，一层一层的遍历完毕之后，我们即可得到每一层的数据结果
这其实就是广度优先算法 BFS
相信通过查看上述编码的备注，应该的都是看的明白的
四、总结：
这里的时间复杂度其实也能看的出来，就是树中包含节点的个数，是 O(n)，我们在遍历的过程中，就是遍历队列的长度，正好是所有节点的总数，因此，空间复杂度也是 O(n)
原题地址：429. N 叉树的层序遍历
今天就到这里，学习所得，若有偏差，还请斧正
欢迎点赞，关注，收藏
朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力
好了，本次就到这里
技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。
我是阿兵云原生，欢迎点赞关注收藏，下次见~
