[Leetcode] Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

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

树的层次遍历，用一个list保存当前层的信息，用另一个list按照顺序保存其所有节点的孩子的信息，然后swap直到没有节点。也可以使用一个队列来保存遍历的结果，插入一个dummy节点来实现分层的效果。

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        List<TreeNode> level1 = new ArrayList<TreeNode>();
        List<TreeNode> level2;
        if(root == null) {
            return result;
        }
        
        level1.add(root);
        while(level1.size() != 0) {
            level2 = new ArrayList<TreeNode>();
            List<Integer> list = new ArrayList<Integer>();
            for(TreeNode node : level1) {
                list.add(node.val);
                if(node.left != null)
                    level2.add(node.left);
                if(node.right != null)
                    level2.add(node.right);
            }
            result.add(list);
            level1 = level2;
        }
        
        return result;
    }

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        List<TreeNode> qu = new ArrayList<TreeNode>();
        List<Integer> list = new ArrayList<Integer>();
        if(root == null) return result;
        TreeNode dummy = new TreeNode(0);
        qu.add(root); qu.add(dummy);
        while(qu.size() != 0) {
            TreeNode node = qu.get(0);
            qu.remove(0);
            if(node == dummy) {
                result.add(list);
                if(qu.size() != 0) {
                    list = new ArrayList<Integer>();
                    qu.add(dummy);
                }
            }
            else {
                list.add(node.val);
                if(node.left != null) qu.add(node.left);
                if(node.right != null) qu.add(node.right);
            }
        }
        return result;
    }

Today, I saw that someone was asked to implement the recursive version of the level traversal, here is the code. The main idea is to use hashmap store each level's information and use post-order traversal to sweep all nodes.

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        HashMap<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
        if(root == null)
            return result;
        dfs(root, 1, map);
        int num = map.keySet().size();
        for(int i = 1; i <= num; i++) {
            result.add(new ArrayList<Integer>(map.get(i)));
        }
        return result;
    }
    
    private void dfs(TreeNode root, int level, HashMap<Integer, List<Integer>> map) {
        if(root == null)
            return;
        if(map.containsKey(level) == true) {
            map.get(level).add(root.val);
        }
        else {
            List<Integer> list = new ArrayList<Integer>();
            list.add(root.val);
            map.put(level, list);
        }
        
        dfs(root.left, level+1, map);
        dfs(root.right, level+1, map);
    }