LeetCode102.二叉树的层序遍历（按层输出和统一输出）

本文主要是介绍LeetCode102.二叉树的层序遍历（按层输出和统一输出），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

LeetCode102.二叉树的层序遍历

文章目录

- LeetCode102.二叉树的层序遍历
- - 1.问题
  - 2.思路
  - - （1）什么是层次遍历
    - （2）借助队列执行
  - 3.代码实现
  - - a.按层输出版
    - b.统一输出版

1.问题

在这里插入图片描述

2.思路

（1）什么是层次遍历

按照层数由小到大，同层由左向右的次序访问结点

实现：（需借助队列！）

在第i层上若结点x在结点y的左边，则x一定在y之前被访问。并且，在第i+1层上，x的子节点一定在y的子节点之前被访问。

（2）借助队列执行

在这里插入图片描述

运行实例：
在这里插入图片描述

3.代码实现

按层输出，就是上图中按[[A] [BC] [DEF]]的格式输出。
统一输出，就是[ABCDEF]的格式。

a.按层输出版

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {queue<TreeNode*> que;if (root != NULL) que.push(root);vector<vector<int>> result;while (!que.empty()) {int size = que.size();vector<int> vec;// 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的for (int i = 0; i < size; i++) {//size表示按层序遍历 因为每次队列里都只留了一层的数据 TreeNode* node = que.front();que.pop();vec.push_back(node->val);if (node->left) que.push(node->left);if (node->right) que.push(node->right);}result.push_back(vec);}return result;}
};

b.统一输出版

上面的代码改一下就可以

//这样可以输出层序遍历序列，但是不能按层输出。 class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {queue<TreeNode*> que;if (root != NULL) que.push(root);vector<vector<int>> result;vector<int> vec;while (!que.empty()) {//int size = que.size();//把关于层次的去掉就可以//for (int i = 0; i < size; i++) {TreeNode* node = que.front();que.pop();vec.push_back(node->val);if (node->left) que.push(node->left);//result.push_back(vec);if (node->right) que.push(node->right);//}}result.push_back(vec);return result;}
};