429. N叉树的层序遍历

问题

给定一个 N 叉树,返回其节点值的层序遍历。 (即从左到右,逐层遍历)。
例如,给定一个 3叉树 :

返回其层序遍历:

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

 
说明:

树的深度不会超过 1000。
树的节点总数不会超过 5000。

解法

既然是层序遍历,那么自然而然的考虑用队列处理。只需要处理好边界条件就可以了。没难度

代码

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 {
    private List<List<Integer>> results = new LinkedList<>();
    public List<List<Integer>> levelOrder(Node root) {
        //如果root为空,直接返回
        if (root == null) {
            return results;
        }
        //创建一个deque。
        Deque<Node> queue = new LinkedList<>();
        //root入队
        queue.offer(root);
        while(!queue.isEmpty()) {
            //每次大循环开始时的队列长度为当前层的元素数量。
            int length = queue.size();
            List<Integer> result = new ArrayList<>(length);
            
            while (length-- >0) {
                //出队
                Node node = queue.pop();
                //设置val
                result.add(node.val);
                //将儿子入队
                queue.addAll(node.children);
            }
            results.add(result);
        }
        return results;
    }
}
2019/07/16 21:20 下午 posted in  广度优先遍历 bfs leetcode