【刷题日记】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 叉树的层序遍历

今天就到这里，学习所得，若有偏差，还请斧正

欢迎点赞，关注，收藏

朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力

好了，本次就到这里

技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。

我是阿兵云原生，欢迎点赞关注收藏，下次见~