算法
(BFS) $O(n)$
利用队列保存层次遍历的节点,
在每一层分别统计元素个数,将该层元素的子节点放入队列,
设置$flag$标签表示该层是顺序输出还是逆序输出,每遍历完一层,就将$flag$切换
Java 代码
class Solution {
public List<List<Integer>> printFromTopToBottom(TreeNode root) {
List<List<Integer>> ret = new ArrayList<>();
Queue<TreeNode> q = new ArrayDeque<>();
if (root == null) return ret;
q.offer(root);
int flag = -1;
while (q.size() > 0) {
int len = q.size();
List<Integer> tmp = new ArrayList<>();
for (int i = 0; i < len; i ++) {
TreeNode p = q.poll();
tmp.add(p.val);
if (p.left != null) q.offer(p.left);
if (p.right != null) q.offer(p.right);
}
if (flag > 0) Collections.reverse(tmp);
ret.add(tmp);
flag *= (-1);
}
return ret;
}
}