AcWing 44. 分行从上往下打印二叉树(java版)
原题链接
中等
作者:
Emt-lin
,
2019-09-23 20:59:12
,
所有人可见
,
阅读 1573
java 代码
class Solution {
public List<List<Integer>> printFromTopToBottom(TreeNode root) {
//定义一个返回集合
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
//采用宽度遍历装元素的队列
Queue<TreeNode> q = new LinkedList<>();
q.add(root);
//采用加入null,来标志本层元素已经遍历完
q.add(null);
//初始化一个装元素的集合
List<Integer> level = new ArrayList<>();
//队列不为空,就继续遍历
while (q.size() != 0){
//出队首元素
TreeNode t = q.poll();
//如果出的队首元素为null,
if (t == null){
//并且如果level集合大小为0,说明整个树已经遍历完了,直接退出循环即可
if (level.size() == 0) break;
//否则说明当前层的所有节点已经遍历完,添加当前层所有元素到返回集合中
//这里创建一个新的集合的原因:就是res这个集合的为一个集合元素 还是一直对 level集合保持引用关系
//如果level改变,res集合里面的每一个都会对应改变。下面就是打印的res集合(不创建新的容器时)
//[[8]]
//[[12, 2], [12, 2]]
//[[6], [6], [6]]
//[[4], [4], [4], [4]]
//[[], [], [], []]
List<Integer> tmp = new ArrayList<>(level);
res.add(tmp);
//并添加一个null标志
q.add(null);
//清除集合所有元素,为了下一层元素进入
level.clear();
//直接进入下一次循环,因为当前元素是null
continue;
}
//添加当前元素值进入集合
level.add(t.val);
if (t.left != null) q.add(t.left);
if (t.right != null) q.add(t.right);
}
return res;
}
}
太牛了
真的太牛逼了
为什么要加上这句: List[HTML_REMOVED] tmp = new ArrayList<>(level);
直接add level为撒不可?
这个是很久以前写的了。原因在注释中写的很清楚(应该)。
可以看看下面写的这个方式。
对了,你需要用markdown语法来发代码。
List<Integer> level = new ArrayList<>();
因为<>,这种会被转换成其他的。
感谢回复,有点get到了,直接add(level)的话,当level每次改变时,其实就影响了res的值,于是最后显示为空。是这个意思吗?
对滴