1
2
3
4
5
6
7
8
9
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

dfs:

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

Level order: instinct: bfs.

Standard queue: Add root node to queue, while not empty, for loop.

q.poll() and q.offer() should be both inside for loop (inside while), because all nodes on this level should be polled and head to next level.(In fact, if TreeNode node = q.poll() is inside for loop while 2 q.offer(node.left/right) is not inside for loop: cannot find symbol

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new LinkedList<List<Integer>>();
        if (root == null) return res;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            // 要根据q的大小进行后面的for循环次数的判断
            int count = q.size();
            List<Integer> tmp = new LinkedList<>();
            for (int i = 0; i < count; ++i) {
                TreeNode node = q.poll();
                tmp.add(node.val);
                if (node.left != null) q.offer(node.left);
                if (node.right != null) q.offer(node.right);
            }
            res.add(tmp);
        }
        return res;
    }
}

More concise:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new LinkedList<List<Integer>>();
        if (root == null) return res;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            List<Integer> tmp = new LinkedList<>();
            int count = q.size();
            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);
            }
            res.add(tmp);
        }
        return res;
    }
}

两种方法，可以看出dfs中的depth和bfs中的count其实是完全不同的，dfs每次都是left child一直走完整个深度，每次加入的一维数组都是只加了一个元素；但是bfs是每次都加完一整层，一次弄完整层所有的node.

Note: Queue(interface) methods: offer, poll, peek should be distinguished from List(interface) methods add, remove, etc.