Binary Tree Level Order Traversal

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]
] 

Naive Way: 一看就觉得这不是BFS吗。用以前的做法，用queue进行BFS遍历，用一个Map存节点对应的层数。

不知道是不是应该有更好的做法。

/**

 * Definition for binary tree

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode(int x) { val = x; }

 * }

 */

public class Solution {

    public List<List<Integer>> levelOrder(TreeNode root) {

        List<List<Integer>> rlst = new ArrayList<List<Integer>>();

        Map<TreeNode, Integer> map = new HashMap<TreeNode, Integer>();

        Queue<TreeNode> queue = new LinkedList<TreeNode>();

        if(root==null){return rlst;}

        queue.add(root);

        map.put(root,0);

        while(!queue.isEmpty()){

            TreeNode node = queue.poll();

            int layer = map.get(node);

            List<Integer> list;

            if(rlst.size() > layer){

                list = rlst.get(layer);

            }else{

                list = new ArrayList<Integer>();

                rlst.add(list);

            }

            rlst.get(layer).add(node.val);

            if(node.left!=null){

                queue.add(node.left);

                map.put(node.left, layer+1);

            }

            if(node.right!=null){

                queue.add(node.right);

                map.put(node.right, layer+1);

            }

        }

        return rlst;

    }

}