问题：

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,null,null,15,7],

    3   / \  9  20    /  \   15   7

return its level order traversal as:

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

解决：

① 用BFS遍历该树即可。

/**

 * Definition for a binary tree node.  * public class TreeNode {  *     int val;  *     TreeNode left;  *     TreeNode right;  *     TreeNode(int x) { val = x; }  * }  */ class Solution { //2ms     public List<List<Integer>> levelOrder(TreeNode root) {         List<List<Integer>> res = new ArrayList<>();         if(root == null) return res;         Queue<TreeNode> queue = new LinkedList<>();         queue.offer(root);         while(! queue.isEmpty()){             int count = queue.size();             List<Integer> tmp = new ArrayList<>();             for (int i = 0;i < count ;i ++ ) {                 TreeNode node = queue.poll();                 tmp.add(node.val);                 if(node.left != null) queue.offer(node.left);                 if(node.right != null) queue.offer(node.right);             }             res.add(tmp);         }         return res;     } }

② 使用DFS,记录遍历到的节点所属的层。

class Solution {//1ms

    public List<List<Integer>> levelOrder(TreeNode root) {         List<List<Integer>> res = new ArrayList<List<Integer>>();         dfs(root, 0, res);         return res;     }     public void dfs(TreeNode root, int level, List<List<Integer>> res) {         if (root == null) return;         if (level >= res.size()) { //确保不会把额外的链表加入到res中

            res.add(new ArrayList<Integer>());

        }         res.get(level).add(root.val);         dfs(root.left, level + 1, res);         dfs(root.right, level + 1, res);     } }