题目描述（中等难度）

二叉树的层次遍历，输出一个 list 的 list。

解法一 DFS

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

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> ans = new ArrayList<>(); 
    DFS(root, 0, ans);
    return ans;
}

private void DFS(TreeNode root, int level, List<List<Integer>> ans) {
    if(root == null){
        return;
    }
    //当前层数还没有元素，先 new 一个空的列表
    if(ans.size()<=level){
        ans.add(new ArrayList<>());
    }
    //当前值加入
    ans.get(level).add(root.val);

    DFS(root.left,level+1,ans);
    DFS(root.right,level+1,ans);
}

解法二 BFS 队列

如果是顺序刷题，前边的 “> 98 题，public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> ans = new ArrayList<>(); if (root == null) { return ans; } Queue<TreeNode> treeNode = new LinkedList<>(); Queue<Integer> nodeLevel = new LinkedList<>(); treeNode.offer(root); int level = 0; nodeLevel.offer(level); while (!treeNode.isEmpty()) { TreeNode curNode = treeNode.poll(); int curLevel = nodeLevel.poll(); if (curNode != null) { if (ans.size() <= curLevel) { ans.add(new ArrayList<>()); } ans.get(curLevel).add(curNode.val); level = curLevel + 1; treeNode.offer(curNode.left); nodeLevel.offer(level); treeNode.offer(curNode.right); nodeLevel.offer(level); } } return ans; }

方案二

参考public List<List<Integer>> levelOrder(TreeNode root) { Queue<TreeNode> queue = new LinkedList<TreeNode>(); List<List<Integer>> ans = new LinkedList<List<Integer>>(); if (root == null) return ans; queue.offer(root); while (!queue.isEmpty()) { int levelNum = queue.size(); // 当前层元素的个数 List<Integer> subList = new LinkedList<Integer>(); for (int i = 0; i < levelNum; i++) { TreeNode curNode = queue.poll(); if (curNode != null) { subList.add(curNode.val); queue.offer(curNode.left); queue.offer(curNode.right); } } if(subList.size()>0){ ans.add(subList); } } return ans; }

总