题目描述（中等难度）

102. Binary Tree Level Order Traversal - 图1

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

解法一 DFS

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

  1. public List<List<Integer>> levelOrder(TreeNode root) {
  2.     List<List<Integer>> ans = new ArrayList<>(); 
  3.     DFS(root, 0, ans);
  4.     return ans;
  5. }
  7. private void DFS(TreeNode root, int level, List<List<Integer>> ans) {
  8.     if(root == null){
  9.         return;
  10.     }
  11.     //当前层数还没有元素，先 new 一个空的列表
  12.     if(ans.size()<=level){
  13.         ans.add(new ArrayList<>());
  14.     }
  15.     //当前值加入
  16.     ans.get(level).add(root.val);
  18.     DFS(root.left,level+1,ans);
  19.     DFS(root.right,level+1,ans);
  20. }

解法二 BFS 队列

如果是顺序刷题，前边的 97 题， 98 题，101 题，都用到了 BFS ，应该很熟悉了。

之前我们用一个 while 循环，不停的从队列中拿一个节点，并且在循环中将当前取出来的节点的左孩子和右孩子也加入到队列中。

相比于这道题，我们要解决的问题是，怎么知道当前节点的 level 。

1. 第一种方案

定义一个新的 class，class 里边两个成员 node 和 level，将我们新定义的 class 每次加入到队列中。或者用一个新的队列和之前的节点队列同步入队出队，新的队列存储 level。

下边的代码实现后一种。

  1. public List<List<Integer>> levelOrder(TreeNode root) {
  2.     List<List<Integer>> ans = new ArrayList<>();
  3.     if (root == null) {
  4.         return ans;
  5.     }
  6.     Queue<TreeNode> treeNode = new LinkedList<>();
  7.     Queue<Integer> nodeLevel = new LinkedList<>();
  8.     treeNode.offer(root);
  9.     int level = 0;
  10.     nodeLevel.offer(level);
  11.     while (!treeNode.isEmpty()) {
  12.         TreeNode curNode = treeNode.poll();
  13.         int curLevel = nodeLevel.poll();
  14.         if (curNode != null) {
  15.             if (ans.size() <= curLevel) {
  16.                 ans.add(new ArrayList<>());
  17.             }
  18.             ans.get(curLevel).add(curNode.val);
  19.             level = curLevel + 1;
  20.             treeNode.offer(curNode.left);
  21.             nodeLevel.offer(level);
  22.             treeNode.offer(curNode.right);
  23.             nodeLevel.offer(level);
  24.         }
  25.     }
  26.     return ans;
  27. }

方案二

参考这里。

我们在 while 循环中加一个 for 循环，循环次数是循环前的队列中的元素个数即可，使得每次的 while 循环出队的元素都是同一层的元素。

for 循环结束也就意味着当前层结束了，而此时的队列存储的元素就是下一层的所有元素了。

  1. public List<List<Integer>> levelOrder(TreeNode root) {
  2.     Queue<TreeNode> queue = new LinkedList<TreeNode>();
  3.     List<List<Integer>> ans = new LinkedList<List<Integer>>();
  4.     if (root == null)
  5.         return ans;
  6.     queue.offer(root);
  7.     while (!queue.isEmpty()) {
  8.         int levelNum = queue.size(); // 当前层元素的个数
  9.         List<Integer> subList = new LinkedList<Integer>();
  10.         for (int i = 0; i < levelNum; i++) {
  11.             TreeNode curNode = queue.poll();
  12.             if (curNode != null) {
  13.                 subList.add(curNode.val); 
  14.                 queue.offer(curNode.left);
  15.                 queue.offer(curNode.right);
  16.             }
  17.         }
  18.         if(subList.size()>0){
  19.             ans.add(subList);
  20.         }
  21.     }
  22.     return ans;
  23. }

总

考察的知识点就是二叉树的 BFS，解法二的方案二是自己不曾想到的， while 循环中加入一个 for 循环，很妙！

windliang wechat

添加好友一起进步~

如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情