题目链接

LeetCode

题目描述

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

例如，以下二叉树层次遍历的结果为：1,2,3,4,5,6,7

32.1 从上往下打印二叉树 - 图1

解题思路

使用队列来进行层次遍历。

不需要使用两个队列分别存储当前层的节点和下一层的节点，因为在开始遍历一层的节点时，当前队列中的节点数就是当前层的节点数，只要控制遍历这么多节点数，就能保证这次遍历的都是当前层的节点。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  8.  * };
  9.  */
  10. class Solution {
  11. public:
  12.     vector<int> levelOrder(TreeNode* root) {
  13.         // 当树为空时，直接返回
  14.         if(root==NULL) return {};
  15.         queue<TreeNode*> qu;
  16.         vector<int> ret;
  17.         qu.push(root);
  18.         while(!qu.empty()){
  19.             TreeNode *tmp = qu.front();
  20.             qu.pop();
  21.             // 顺序输出结点值
  22.             ret.push_back(tmp->val);
  23.             // 将左右非空结点加入队列
  24.             if(tmp->left!=NULL) qu.push(tmp->left);
  25.             if(tmp->right!=NULL) qu.push(tmp->right);
  26.         }
  27.         return ret;
  28.     }
  29. };
  • 时间复杂度 O(N) ： N 为二叉树的节点数量，即 BFS 需循环 N 次。
  • 空间复杂度 O(N) ： 最差情况下，即当树为平衡二叉树时，最多有 N/2 个树节点同时在 queue 中，使用 O(N) 大小的额外空间。