429. N 叉树的层序遍历
解题思路
定义节点类: 首先定义了一个节点类 Node,每个节点包含一个整数值 val 和一个子节点列表 children。
实现层序遍历方法: 在 Solution 类中,定义了一个 levelOrder 方法用于执行多叉树的层序遍历。首先检查根节点是否为空,如果为空则直接返回空列表。然后,使用一个队列来辅助层序遍历,将根节点加入队列。
遍历每一层: 使用一个循环,直到队列为空。在每一轮循环中,首先获取当前队列的大小,这个大小表示当前层的节点数。然后创建一个临时列表用于存储当前层的节点值。
处理当前层节点: 在内部循环中,从队列中依次弹出当前层的节点,并将其值添加到临时列表中。同时,将当前节点的所有子节点加入队列中。
收集当前层结果: 当内部循环结束后,当前层的节点值已经全部添加到临时列表中,将这个列表添加到结果列表中。
返回结果: 最终返回结果列表,其中包含了每一层的节点值组成的二维列表
/*
// 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 {
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> levelOrder(Node root) {
if(root == null){
return new ArrayList<>();
}
Queue<Node> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
int size = queue.size();
List<Integer> temp = new ArrayList<>();// 收集当前层的节点
for(int i = 0; i < size; i++){
// 节点出队
Node cur = queue.poll();
temp.add(cur.val);// 添加当前层的节点
// 将它的所有孩子节点全部入队
for(Node node:cur.children){
queue.offer(node);
}
}
res.add(temp);
}
return res;
}
}