Java——N叉树的层序遍历

题目链接

leetcode在线oj题——N叉树的层序遍历

题目描述

给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。

树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。

题目示例

示例1:

输入：root = [1,null,3,2,4,null,5,6]
输出：[[1],[3,2,4],[5,6]]

示例2:

输入：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]

输出：[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]

题目提示

• 树的高度不会超过 1000
• 树的节点总数在 [0, 10^4] 之间

解题思路

首先判断树的根节点是不是空，如果是空则直接返回空

然后建立一个队列，先将根节点放进去

然后确定当前队列大小size，此时只有一个元素，将队列的前size个元素（根节点）的所有孩子节点都放进队列，将队列的前size个元素取出来并打印

重复上面的过程，将队列的前size个元素（3节点，2节点，4节点）的孩子节点都放入队列，将队列的前size个元素取出来并打印

一直重复上面的过程，将队列的前size个元素的所有孩子放进队列，然后将队列的前size个元素取出并打印出来，直到最后队列为空，即可得到最终的结果

代码

/*
// Definition for a Node.
class Node {public int val;public List<Node> children;public Node() {}public Node(int _val) {val = _val;}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.offer(root);while(!queue.isEmpty()){List<Integer> rowList = new ArrayList<>();int size = queue.size();while(size != 0){Node cur = queue.poll();//保存当前元素valrowList.add(cur.val);//添加孩子节点for (int i = 0; i < cur.children.size(); i++) {queue.offer(cur.children.get(i));}size--;}result.add(rowList);}return result;}
}