从上到下打印二叉树II

---

题目：

题解：

• 解题思路：借助 队列 的先入先出特性。 将本层全部节点打印到一行，并将下一层全部节点加入队列，以此类推，即可分为多行打印。

  • 参考 从上到下打印二叉树 - 轩辕&小站中加入一层循环，将上一次放入栈的所有结点都输出。

• 复杂度分析：

  • 时间复杂度 O(N)： N 为二叉树的节点数量，即 BFS 需循环 N 次。
  • 空间复杂度 O(N) ： 最差情况下，即当树为平衡二叉树时，最多有 N/2 个树节点同时在 queue 中，使用 O(N) 大小的额外空间。

• 代码：

   class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
  
  class Solution {
      public List<List<Integer>> levelOrder(TreeNode root) {
          if (root == null) {
              return new ArrayList<>();
          }
  
          // 初始化队列
          Queue<TreeNode> queue  = new LinkedList() {{ add(root); }};
          // 初始化返回的list
          List<List<Integer>> list = new ArrayList<>();
          
          while (!queue.isEmpty()) {
              List<Integer> tmp = new ArrayList<>();
              // 这样避免了因为queue的值改变，queue.size()变化而报错的情况
              // 或者可以这样解决
              /*
              * int currentLevelSize = queue.size();
              * for (int i = 1; i <= currentLevelSize; ++i){...}
              * */
              for (int i = queue.size(); i > 0; i--) {
                  TreeNode poll = queue.poll();
                  tmp.add(poll.val);
                  if (poll.left != null) {
                      queue.add(poll.left);
                  }
                  if (poll.right != null) {
                      queue.add(poll.right);
                  }
              }
              list.add(tmp);
          }
          return list;
      }
  }