429. N-ary Tree Level Order Traversal

Leetcode Tree Breath-first Search Stack

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:

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.

分析

这道题目是102. Binary Tree Level Order Traversal的扩展，将一棵树的子节点的数目从2增加到了任意。其实只要在遍历的时候，依次遍历子节点就行了。

public List<List<Integer>> levelOrder(Node root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) return res;
    Queue<Node> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            Node node = queue.poll();
            list.add(node.val);
            for (Node child: node.children)
                if (child != null) queue.offer(child);
        }
        res.add(list);
    }
    return res;
}