429 N-ary Tree Level Order Traversal N叉树的层序遍历

Description:
Given an n-ary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example, given a 3-ary tree:

3-ary tree

We should return its level order traversal:

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

Note:

The depth of the tree is at most 1000.
The total number of nodes is at most 5000.

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

例如，给定一个 3叉树 :

3叉树

返回其层序遍历:

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

思路:

参考LeetCode #107 Binary Tree Level Order Traversal II 二叉树的层次遍历 II
时间复杂度O(n), 空间复杂度O(n)

代码:
C++:

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution 
{
public:
    vector<vector<int>> levelOrder(Node* root) 
    {
        vector<vector<int>> result;
        if (!root) return result;
        queue<Node*> q;
        q.push(root);
        while (!q.empty()) 
        {
            vector<int> temp;
            for (int i = 0, s = q.size(); i < s; i++) 
            {
                Node* cur = q.front();
                temp.push_back(cur -> val);
                for (int j = 0; j < cur -> children.size(); j++) q.push(cur -> children[j]);
                q.pop();
            }
            result.push_back(temp);
        }
        return result;
    }
};

Java:

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val,List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            List<Integer> temp = new ArrayList<>();
            int len = queue.size();
            for (int i = 0; i < len; i++) {
                Node t = queue.poll();
                temp.add(t.val);
                for (int j = 0; j < t.children.size(); j++) queue.add(t.children.get(j));
            }
            result.add(temp);
        }
        return result;
    }
}

Python:

"""
# 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: 'Node') -> List[List[int]]:
        result = []
        def dfs(root: 'Node', depth: int) -> None:
            if not root: 
                return 
            if len(result) <= depth:
                result.append([])
            result[depth].append(root.val)
            for c in root.children:
                dfs(c, depth + 1)
        dfs(root, 0)
        return result