二叉树的层次遍历c++树的方法
时间: 2024-06-13 12:06:56 浏览: 134
以下是C++语言实现二叉树层次遍历的方法:
```c++
#include <iostream>
#include <queue>
using namespace std;
// 定义二叉树结构体
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 层次遍历函数
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
if (!root) {
return res;
}
queue<TreeNode*> q{{root}};
while (!q.empty()) {
vector<int> oneLevel;
for (int i = q.size(); i > 0; --i) {
TreeNode* t = q.front(); q.pop();
oneLevel.push_back(t->val);
if (t->left) {
q.push(t->left);
}
if (t->right) {
q.push(t->right);
}
}
res.push_back(oneLevel);
}
return res;
}
// 测试
int main() {
TreeNode* root = new TreeNode(3);
root->left = new TreeNode(9);
root->right = new TreeNode(20);
root->right->left = new TreeNode(15);
root->right->right = new TreeNode(7);
vector<vector<int>> res = levelOrder(root);
for (auto& level : res) {
for (auto& val : level) {
cout << val << " ";
}
cout << endl;
}
return 0;
}
```
阅读全文