［抄题］：
给出一棵二叉树，返回其节点值的层次遍历（逐层从左往右访问）
［思维问题］：
［一句话思路］：
用queue存每一层
［输入量］：空： 正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：
［画图］：
［一刷］：
- 每一层level存的东西都是不一样的，所以要在queue非空的循环中再新建。不要当成全局变量。
- root为空时，返回result空数组，而不是null四个字母
- stack用pop 弹出来,queue用poll 拉出来，想想也比较形象。root非空用null，数据结构非空要用isEmpty()函数
［二刷］：
- 不要忘了写特判
［三刷］：
［四刷］：
［五刷］：
［总结］：
把size单独设成变量 ，每次都取一遍 多取几次总不会错 （否则取左、右会导致queue.size()很大，level会多加）
树的BFS不会重复，所以不需要用哈希表。只要用queue即可。
［复杂度］：Time complexity: O(n) Space complexity: O(n)
［英文数据结构或算法，为什么不用别的数据结构或算法］：
- 用queue存每一层，实现先进先出
- 注意格式：接口 名 = new 具体实现；eg 队列可以用静态数组、链表linked list来实现
- List<List<Integer>> result = new ArrayList<List<Integer>>(); list里面装list，效果是一层一层的：
[
[3],
[9,20],
[15,7]
]［其他解法］：
2queue，dummy node
［Follow Up］：
- 把结果反过来写：用Collections.reverse(result);函数
- DFS:迭代式的深度优先搜索，不断放宽MAX_LEVEL条件，直到某层没有点。（历史上，内存有限的时候用）
［LC给出的题目变变变］：
637. Average of Levels in Binary Tree
103. Binary Tree Zigzag Level Order Traversal
public class Solution {
/*
* @param root: A Tree
* @return: Level order a list of lists of integer
*/
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
Queue<TreeNode> queue = new LinkedList<TreeNode>();
if (root == null) {
return result;
}
queue.offer(root);
while (!queue.isEmpty()) {//
int size = queue.size();
List<Integer> level = new ArrayList<Integer>();
for (int i = 0; i < size; i++) {
TreeNode curt = queue.poll();//
level.add(curt.val);
if (curt.left != null) {
queue.offer(curt.left);
}
if (curt.right != null) {
queue.offer(curt.right);
}
}
result.add(level);
}
return result;
}
}