leetcode讲解--429. N-ary Tree Level Order Traversal

题目

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:

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

[题目地址]https://leetcode.com/problems...

讲解

这道题我真的想了有很久，刚开始想用队列，但是发现不知道怎么分割每一层，于是就想还是用递归。后来越发想不明白，最后看了别人的解法。其实分割每一层是可以做到的。以后要多练习。

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 {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    public List<List<Integer>> levelOrder(Node root) {
        if(root==null){
            return result;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        int children_num = 1;
        List<Integer> rootList = new ArrayList<Integer>();
        rootList.add(root.val);
        result.add(rootList);
        while(!queue.isEmpty()){
            List<Integer> list = new ArrayList<>();
            int count=0;
            for(int i=0;i<children_num;i++){
                Node now = queue.poll();
                if(now.children!=null){
                    for(Node node:now.children){
                        queue.offer(node);
                        list.add(node.val);
                        count++;
                    }
                }
            }
            children_num = count;
            if(list.size()>0){
                result.add(list);
            }
        }
        return result;
    }
}