1
2
3
4
5
6
7
8
9
10
11
    3
   / \
  9  20
    /  \
   15   7

[
  [3],
  [9,20],
  [15,7]
]

实际上dfs中的level和bfs中的count都是一个意思，并不是摆设，而是用来约束遍历/递归的次数的

bfs iterative: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        if (root == null) return list;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            int count = q.size();
            List<Integer> tmp = new LinkedList<>();
            for (int i = 0; i < count; ++i) {
                if (q.peek().left != null) q.offer(q.peek().left);
                if (q.peek().right != null) q.offer(q.peek().right);
                tmp.add(q.poll().val);
            }
            list.add(tmp);
        }
        
        return list;
    }
}

dfs recursive:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        dfs(list, 0, root);
        return list;
    }
    
    public void dfs(List<List<Integer>> list, int level, TreeNode root) {
        if (root == null) return;
        if (list.size() == level) list.add(new ArrayList<>());
        list.get(level).add(root.val);
        if (root.left != null) dfs(list, level + 1, root.left);
        if (root.right != null) dfs(list, level + 1, root.right);
    }
}