2021/05/04
这道题的难点不在层次遍历，而在于怎么知道每一层有多少个结点。
答案是，每一次 while 循环时，当前队列的长度就是当前级别有多少个元素，可以用数学归纳法证明。
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
if (root == null) return Collections.emptyList();
Queue<TreeNode> q = new LinkedList<>();
TreeNode p = root;
q.offer(p);
List<List<Integer>> res = new ArrayList<>();
while (!q.isEmpty()) {
List<Integer> cur = new ArrayList<>();
int levelSize = q.size();
for (int i = 0; i < levelSize; i++) {
p = q.poll();
cur.add(p.val);
if (p.left != null) q.offer(p.left);
if (p.right != null) q.offer(p.right);
}
res.add(cur);
}
return res;
}
}