Clone N-ary Tree Python Solution with Tests

lcpy gen -n 1490   # by problem number
lcpy gen -s clone_n_ary_tree   # by problem name

class Node {
    public int val;
    public List<Node> children;
}

Input: root = [1,null,3,2,4,null,5,6]
Output: [1,null,3,2,4,null,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,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,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(n)
    def clone_tree(self, root: NaryNode | None) -> NaryNode | None:
        if root is None:
            return None
        clones: dict[NaryNode, NaryNode] = {root: NaryNode(root.val)}
        queue: deque[NaryNode] = deque([root])
        while queue:
            node = queue.popleft()
            for child in node.children:
                clones[child] = NaryNode(child.val)
                clones[node].children.append(clones[child])
                queue.append(child)
        return clones[root]