102. 二叉树的层序遍历
BPS
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> vec_all;
//如果为空, 直接返回
if(root == nullptr) return vec_all;
//使用队列保存每层的所有节点，每次把队列里的原先所有节点进行出队列操作，再把每个元素的非空左右子节点进入队列。因此即可得到每层的遍历。
//怎么知道是在这一层呢? 关键是每一次循环都设一个size,没pop一次就size--
queue<TreeNode*> que;
TreeNode* cur = root;
//第一层入队
que.emplace(cur);
//如果队列为空, 就退出循环
while(!que.empty())
{
//如果这一层的元素遍历完了, 就退出循环
int size = que.size();
//存放一层的数据
vector<int> vec;
while(size--)
{
//插入队首元素
vec.emplace_back(que.front()->val);
//如果队首有子节点, 插入到que中
if(que.front()->left!=nullptr) que.emplace(que.front()->left);
if(que.front()->right!=nullptr) que.emplace(que.front()->right);
//删除队首节点
que.pop();
}
//将一层放入vec_all中汇总
vec_all.emplace_back(vec);
}
return vec_all;
}
};
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
//辅助函数
void pre_order(vector<int>& vec, TreeNode* cur)
{
//递归终止
if(cur == nullptr) return;
//前序遍历就是最先打印出来
vec.push_back(cur->val);
//递归关系
pre_order(vec, cur->left);
pre_order(vec, cur->right);
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> vec;
TreeNode* cur = root;
pre_order(vec, cur);
return vec;
}
};
循环(待续)
ps: 中序和后序就是在递归的中间和后面打印出来