题目描述
给定一个 N 叉树，返回其节点值的层序遍历。 (即从左到右，逐层遍历)。
例如，给定一个 3叉树 :
返回其层序遍历:
[
[1],
[3,2,4],
[5,6]
]
分析
题目难点主要就在如何把节点一层层的分开。我想到的是用一个temp列表来记录“当前层节点”
然后依次展开当前层节点的所有子节点到一个tempChildren列表中。
顺便把所有当前层节点的值也记录到一个list中。当temp中节点展开完后，也就是temp为空时，则表示当前层所有节点已经遍历完成
此时（temp为空时），把list加入结果中，把tempChildren的值赋给temp.然后回到最开始。直到tempChildren最后为空。也就遍历完成了
代码如下：
/*
// 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>> ans =new LinkedList();
LinkedList<Node> temp= new LinkedList();
LinkedList<Node> tempChildren= new LinkedList();
List<Integer> list = new LinkedList();
if(root==null) return ans;
temp.add(root);
while(!temp.isEmpty()){
Node node=temp.pollFirst();
list.add(node.val);
if(node.children!=null){
for(Node children : node.children){
tempChildren.add(children);
}
}
if(temp.isEmpty()){
ans.add(new LinkedList<>(list));
list.clear();
for (Node nodechildren:tempChildren
) {
temp.add(nodechildren);
}
tempChildren.clear();
}
}
return ans;
}
}
问题--浅拷贝和深拷贝
这个思路是没问题的，可最开始出来的结果总是为空。打断点调试才发现是深浅拷贝的问题
我们来看这段代码
ans.add(new LinkedList<>(list));
list.clear();
for (Node nodechildren:tempChildren
) {
temp.add(nodechildren);
}
tempChildren.clear();
本来我是这样写的
ans.add(list);
list.clear();
temp=tempChildren;
tempChildren.clear();
然后就出现了上述问题，比如本来向ans中添加的list是正常有值的，但是执行list.clear()这个方法后，ans中已经添加的list也会被清空，这是因为在内存中俩个list指向的一块内存。下面的temp和tempChildren同理。所有就改成了第一版代码（ps.网上实现深拷贝的方法感觉都比较复杂，这里的需求也比较简单，就直接new了）
更加优雅的方案
力扣给的官解第一种方法和我的很类似，只是它没有使用tempChildren这个列表。而是把temp变成了队列，然后使用for循环来控制每一层。这里使用队列是有一定好处的，能大幅减低时间复杂度
使用队列十分重要，如果使用 Vector，List，Array 的话，我们删除元素需要 O(n)的时间复杂度。而队列删除元素只需要 O(1)的时间。
下面是具体代码
// This code is a modified version of the code posted by
// #zzzliu on the discussion forums.
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.add(root);
while (!queue.isEmpty()) {
List<Integer> level = new ArrayList<>();
int size = queue.size();
for (int i = 0; i < size; i++) {
Node node = queue.poll();
level.add(node.val);
queue.addAll(node.children);
}
result.add(level);
}
return result;
}
}
这个For循环时很精妙的，其他的和我的代码大差不差。具体解释下这个for循环。
在For循环之前，它先得到了当前队列的长度，这样就可以控制for循环只循环“当前层”。而在for循环内部，又依次删除了“当前层”的所有元素，并把“当前层”的所有子节点展开到队列中，同时记录了当前层的的元素值到level这个列表中。同时注意它这个level列表的定义位置在while内部，也就避免了我上面代码的"浅拷贝"清空的问题。相对来说优雅了很多
其他方案
此外，力扣还给了另外一种方法，简化的广度搜索
// This code is a modified version of the code posted by
// #zzzliu on the discussion forums.
class Solution {
public List<List<Integer>> levelOrder(Node root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) return result;
List<Node> previousLayer = Arrays.asList(root);
while (!previousLayer.isEmpty()) {
List<Node> currentLayer = new ArrayList<>();
List<Integer> previousVals = new ArrayList<>();
for (Node node : previousLayer) {
previousVals.add(node.val);
currentLayer.addAll(node.children);
}
result.add(previousVals);
previousLayer = currentLayer;
}
return result;
}
}
其实我感觉也差不多时一种方法...