429.N叉树的层序遍历

链接：429.N叉树的层序遍历
难度：Medium
标签：树、广度优先搜索
简介：给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。

题解 1 - cpp

• 编辑时间：2022-04-08
• 执行用时：12ms
• 内存消耗：11.5MB
• 编程语言：cpp
• 解法介绍：层序遍历。

class Solution {
   public:
    vector<vector<int>> levelOrder(Node *root) {
        vector<vector<int>> ans;
        if (!root) return ans;
        queue<Node *> q;
        q.push(root);
        int size = 1;
        vector<int> cur;
        while (q.size()) {
            Node *node = q.front();
            q.pop();
            cur.push_back(node->val);
            for (auto child : node->children) q.push(child);
            if (--size == 0) {
                size = q.size();
                ans.push_back(cur);
                cur.clear();
            }
        }
        return ans;
    }
};

题解 2 - python

• 编辑时间：2024-02-17
• 执行用时：54ms
• 内存消耗：18.05MB
• 编程语言：python
• 解法介绍：bfs。

class Solution:
    def levelOrder(self, root: 'Node') -> List[List[int]]:
        if not root: return []
        q = deque() 
        q.append(root)
        size = 1
        ans = [[root.val]]
        while q:
            node = q.popleft()
            for child in node.children: q.append(child)
            size -= 1
            if size == 0:
                size = len(q)
                if q: ans.append([node.val for node in q])
        return ans