给你一个二叉树，请你返回其按层序遍历得到的节点值。 （即逐层地，从左到右访问所有节点）。

示例：二叉树：[3,9,20,null,null,15,7],

  1.     3
  2.    / \
  3.   9  20
  4.     /  \
  5.    15   7

返回其层序遍历结果：

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

解法一 BFS

思路:

大while循环里套一个小while循环，大while循环控制层数，小while循环控制每一层元素的遍历

public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        //当q里有元素的时候进入循环
        //每一次进入这个循环的时候就会开启一个新的层级
        while (q.size()>0){
            //q里元素的个数
            int size = q.size();
            //这个list存每一层上有多少个元素
            ArrayList<Integer> list = new ArrayList<>();
            //当前层所有元素的循环
            while (size > 0){
                TreeNode cur  = q.poll();
                list.add(cur.val);
                //看看左子树有没有元素，有的话加到下一层q
                if (cur.left != null){
                    q.add(cur.left);
                }
                //看看左子树有没有元素，有的话加到下一层q
                if (cur.right != null){
                    q.add(cur.right);
                }
                //控制while循环的指针
                size--;
            }
            result.add(new ArrayList<>(list));
        }
        return null;
    }

解法一 DFS

这道题考的就是 BFS，我们可以通过 DFS 实现。只需要在递归过程中将当前 level 传入即可.

public List<List<Integer>> levelOrder2(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();

        if (root == null){
            return result;
        }
        dfs(root,result,0);
        return  result;
    }

    private void dfs(TreeNode node, List<List<Integer>> result, int level) {
        if (node == null){
            return;
        }
        //当前层数还没有元素，先new一个空的列表
        if(level > result.size()-1){
            result.add(new ArrayList<>());
        }
        //当前值加入
        result.get(level).add(node.val);
            //这里不用判断左右子树是否为空
            //会在下一层的dfs里判断
            dfs(node.left,result,level+1);
            dfs(node.right,result,level+1);
    }