剑指 Offer 32 - I. 从上到下打印二叉树

解题思路

本题要求从上至下打印出二叉树的每一个节点，同一层的节点按照从左至右的顺序进行打印。

如示例：

image.png
该二叉树遍历打印的结果为：[ 3，9，2，5，7 ]

这是一道典型的 BFS 遍历二叉树，BFS 通常使用队列（Queue）先入先出这种特性来实现。

算法流程：

  1. 当树的根节点为空，则直接返回空数组

  2. 初始化队列，将 root 根节点添加到队列中

  3. BFS 循环

    • 队首元素出队，记作 node；
    • 将 node.val 添加到队列列表中；
    • 如果 node 的左（右）节点不为空，则将左（右）节点添加到队列。

代码

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. class Solution {
  11.     public int[] levelOrder(TreeNode root) {
  12.         if(root == null){
  13.             return new int[]{};
  14.         }
  15.         Queue<TreeNode> queue = new LinkedList<>();
  16.         List<Integer> list = new ArrayList<>();
  17.         queue.offer(root);
  18.         while(!queue.isEmpty()){
  19.             root = queue.poll();
  20.             list.add(root.val);
  21.             if(root.left != null){
  22.                 queue.offer(root.left);
  23.             }
  24.             if(root.right != null){
  25.                 queue.offer(root.right);
  26.             }
  27.         }
  28.         return list.stream().mapToInt(Integer::valueOf).toArray();
  29.     }
  30. }

复杂度分析

  • 时间复杂度：O(N)

我们需要将整棵树进行一次遍历，所以时间复杂度为：O(N)

  • 空间复杂度：O(N)

当待遍历的树为一棵平衡二叉树时，最多有 N/2 个节点同时在队列中，所以使用 O(N) 的额外空间