Leetcode __429. N叉树的层序遍历
问题描述
给定一个 N 叉树,返回其节点值的层序遍历。 (即从左到右,逐层遍历)。
例如,给定一个 3叉树 :
返回其层序遍历:
[
[1],
[3,2,4],
[5,6]
]
说明:
树的深度不会超过 1000。
树的节点总数不会超过 5000。
解题思路
跟之前做过的二叉树的层序遍历是一样的,顺序是从上到下,从左到右
- 从上到下:不需要额外操作,list一个一个放就可以维护该顺序
- 从左到右:先进先出,用queue维护该顺序
- 每一层都要新new list,新new的标识就通过那算个变量来控制
实现
/*
// 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 {
public List<List<Integer>> levelOrder(Node root) {
List<List<Integer>> reslist = new LinkedList<List<Integer>>();
List<Integer> list = new LinkedList<Integer>();
if(root==null){
return reslist;
}
int curCount = 0, curNum = 1, nextCount = 1;
Queue<Node> queue = new LinkedList<Node>();
Node t ;
queue.offer(root);
while (!queue.isEmpty()){
t= queue.poll();
list.add(t.val);
if(t.children!=null){
for(Node node :t.children){
if(node!=null){
queue.offer(node);
}
nextCount++;
}
}
if (++curCount == curNum) {
reslist.add(list);//增加元素,每次在0位置插入元素,其他往后顺延
list = new LinkedList<Integer>();
curNum = nextCount;
}
}
return reslist;
}
}
别人实现
运行时间较短
/*
// 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 {
public List<List<Integer>> levelOrder(Node root) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(root == null)
return res;
fillRes(root, 0, res);
return res;
}
public void fillRes(Node root, int level, List<List<Integer>> res) {
if(res.size() < level + 1)
res.add(new ArrayList<Integer>());
res.get(level).add(root.val);
for (Node n : root.children) {
fillRes(n, level + 1, res);
}
}
}
这种做法更容易理解一些,判断新的一样的标志就是结果res.size() < level + 1,这样就新new一个,在把该行的值传进去,遍历子树(孩子节点就是下一层),递归