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

LeetCode102.二叉树的层序遍历

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;}
};