解题思路
广度优先搜索模板题。
广度优先搜索模板
广度优先遍历:
储存遍历结果:List<Integer> res
队列:queue
queue.add(root.val); //把第一层元素放入到队列中
while(queue.size()!=0){
int length = queue.size();
List<Integer> level; //储存这一层所有元素。
for(int i=0;i<length;i++){
node = queue.poll(); //得到队头,同时丢去队头
//把temp扩展的下一层元素都放到队列queue中
if(node.left!=null){}
if(node.right!=null){}
//储存上一层的所有节点
level.add(templ);
}
res.add(level);
}
相关代码
/*
// 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>> res = new ArrayList<>();
Queue<Node> queue = new LinkedList<>();
if(root==null) return res;
queue.add(root);
while(queue.isEmpty()==false){
int len = queue.size();
List<Integer> level = new ArrayList<>();
for(int i=0;i<len;i++){
Node temp = queue.poll();
for(int j=0;j<temp.children.size();j++){
queue.add(temp.children.get(j));
}
level.add(temp.val);
}
res.add(level);
}
return res;
}
}