从上到下打印二叉树

---

题目：

题解：

• 解题思路：判断当队列不为空时，进行将队列中树指针所指向的值有数值的值放入list集合，最后遍历list集合给数组并返回。

• 复杂度分析：

  • 时间复杂度 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 int[] levelOrder(TreeNode root) {
  
          if (root == null) {
              return new int[0];
          }
  
          // 初始化队列，将树的头结点指针放到队列中，{{ add(root); }};是匿名内部方法，相当于queue.add(root);
          Queue<TreeNode> queue  = new LinkedList() {{ add(root); }};
          // 初始化list集合
          ArrayList<Integer> list = new ArrayList<>();
  
          // 判断当队列不为空时，进行将队列中树指针所指向的值有数值的值放入list集合
          while (!queue.isEmpty()) {
              // 移除并返问队列头部的元素,给TreeNode类型，队列里的树的指针根据队列的特性，先进先出，实现广度优先遍历
              TreeNode node = queue.poll();
              System.out.println(node);
              list.add(node.val);
              if (node.left != null) {
                  queue.add(node.left);
              }
              if (node.right != null) {
                  queue.add(node.right);
              }
          }
  
          int[] a = new int[list.size()];
          for (int i = 0; i < list.size(); i++) {
              a[i] = list.get(i);
          }
  
          return a;
      }
  }