题目

难度：★★☆☆☆
类型：二叉树

给定一个 N 叉树，返回其节点值的层序遍历。 (即从左到右，逐层遍历)。

例如，给定一个 3叉树 :

某个三叉树

返回其层序遍历:

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

说明：

树的深度不会超过 1000。
树的节点总数不会超过 5000。

解答

这道题可以说与【题目107. 二叉树的层次遍历】几乎完全相同了，只有两个地方需要改动：

1. 加入下一层结点列表时，不仅有左孩子和右孩子，需要加入所有孩子；

2. 这里不需要逆序返回，所有结果列表按照自顶向下即可。

大家可以注意两题在编码上的区别。

class Solution:
    def levelOrderBottom(self, root):
        res = []                                                # 结果列表
        queue = [root]                                          # 当前层的结点

        while queue:                                            # 当前层存在结点时
            cur_layer = []                                      # 初始化当前层结果列表为空
            next_queue = []                                     # 初始化下一层结点列表为空

            for node in queue:                                  # 遍历当前层的每一个结点
                if node:                                        # 如果该结点不为空，则进行记录
                    cur_layer.append(node.val)                  # 将该结点的值加入当前层结果列表的末尾
                    next_queue.extend(node.children)            # 将该结点的孩子结点加入到下一层结点列表

            if cur_layer:                                       # 只要当前层结果列表不为空
                res.insert(0, cur_layer)                        # 则把当前层结果列表加入到结果列表首端
            queue = next_queue                                  # 更新当前层节点列表为下一层结点列表

        return res                                              # 返回最终结果

如有疑问或建议，欢迎评论区留言~