LeetCode 0429.N 叉树的层序遍历：广度优先搜索(BFS)

【LetMeFly】429.N 叉树的层序遍历：广度优先搜索(BFS)

力扣题目链接：https://leetcode.cn/problems/n-ary-tree-level-order-traversal/

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

树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。

示例 1：

输入：root = [1,null,3,2,4,null,5,6]
输出：[[1],[3,2,4],[5,6]]

示例 2：

输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]

提示：

树的高度不会超过 1000
树的节点总数在 [0, 10^4] 之间

方法一：广度优先搜索(BFS)

和之前二叉树的广度优先搜索一样，我们可以使用一个队列来存放每一层的节点，再让这些节点依次出队，并将节点的孩子们（如有）入队。

时间复杂度 $O (N)$ ，其中 $N$ 是节点个数
空间复杂度 $O (N 2)$ ，其中 $N 2$ 是节点最多的一层的节点数

AC代码

C++

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> ans;
        queue<Node*> q;
        if (root) {
            q.push(root);
        }
        while (q.size()) {
            ans.push_back({});
            for (int _ = q.size(); _ > 0; _--) {
                Node* thisNode = q.front();
                q.pop();
                ans.back().push_back(thisNode->val);
                for (Node* nextNode : thisNode->children) {
                    q.push(nextNode);
                }
            }
        }
        return ans;
    }
};

Python

# from typing import List, Optional

# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children

class Solution:
    def levelOrder(self, root: Optional[Node]) -> List[List[int]]:
        ans = []
        q = []
        if root:
            q.append(root)
        while q:
            ans.append([])
            for _ in range(len(q)):
                thisNode = q[0]
                q = q[1:]
                ans[-1].append(thisNode.val)
                for nextNode in thisNode.children:
                    q.append(nextNode)
        return ans

针对于Python的语法糖，若使用两个数组可以很大程度上减少代码量（甚至提高效率）：

# from typing import Optional, List

# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children

class Solution:
    def levelOrder(self, root: Optional[Node]) -> List[List[int]]:
        ans = []
        a = []
        if root:
            a.append(root)
        while a:
            ans.append([thisNode.val for thisNode in a])
            a = [nextChild for thisNode in a for nextChild in thisNode.children]
        return ans