N-ary Tree Level Order Traversal

lcpy gen -n 429   # by problem number
lcpy gen -s n_ary_tree_level_order_traversal   # by problem name

Input: root = [1,null,3,2,4,null,5,6]
Output: [[1],[3,2,4],[5,6]]

Input: 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]
Output: [[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]

from __future__ import annotations

from collections import deque


class NaryNode:
    def __init__(self, val: int = 0, children: list[NaryNode] | None = None) -> None:
        self.val = val
        self.children = children if children is not None else []


class Solution:
    # Time: O(n)
    # Space: O(w)
    def level_order(self, root: NaryNode | None) -> list[list[int]]:
        levels: list[list[int]] = []
        if root is None:
            return levels
        current: deque[NaryNode] = deque([root])
        while current:
            levels.append([node.val for node in current])
            nxt: deque[NaryNode] = deque()
            for node in current:
                nxt.extend(node.children)
            current = nxt
        return levels