Java
时间复杂度:O(n)
空间复杂度:O(n)
思路:(参考了 extrovert的题解 )
在每一层的最后一个节点加上
null
标记。
如果队列当前元素不为null
,说明未到当前层最后一个节点,继续扩展本层节点的孩子。
如果队列当前元素为null
,说明已到当前层最后一个节点,就将包括当前层所有元素的数组加入到总数组中,并且再new
一个数组给下一层使用。如果当前队列为空的话,说明已到叶子节点层,循环结束;否则,就意味本层的扩展已结束,并在下一层的最后一个节点加上null
标记。
class Solution {
public List<List<Integer>> printFromTopToBottom(TreeNode root) {
Queue<TreeNode> q = new LinkedList<>();
List<List<Integer>> list = new LinkedList<>();
if(root == null) return list;
List<Integer> level = new LinkedList<>();
q.add(root);
q.add(null);
while(q.size() > 0) {
TreeNode now = q.poll();
if(now != null) {
level.add(now.val);
if(now.left != null) q.add(now.left);
if(now.right != null) q.add(now.right);
} else {
if(q.size() > 0) q.add(null);
list.add(level);
level = new LinkedList<>();
}
}
return list;
}
}