C++用层次遍历输出二叉树从根节点到叶子结点的路径
时间: 2024-05-15 11:13:07 浏览: 124
以下是C++代码实现:
```C++
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
// 二叉树节点的定义
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 从根节点到叶子结点的路径
vector<vector<int>> binaryTreePaths(TreeNode* root) {
vector<vector<int>> paths;
if (!root) {
return paths;
}
queue<TreeNode*> nodeQueue;
queue<vector<int>> pathQueue;
nodeQueue.push(root);
pathQueue.push(vector<int>{root->val});
while (!nodeQueue.empty()) {
TreeNode* node = nodeQueue.front();
vector<int> path = pathQueue.front();
nodeQueue.pop();
pathQueue.pop();
if (!node->left && !node->right) {
paths.push_back(path);
} else {
if (node->left) {
nodeQueue.push(node->left);
vector<int> newPath = path;
newPath.push_back(node->left->val);
pathQueue.push(newPath);
}
if (node->right) {
nodeQueue.push(node->right);
vector<int> newPath = path;
newPath.push_back(node->right->val);
pathQueue.push(newPath);
}
}
}
return paths;
}
int main() {
// 构造二叉树
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->right = new TreeNode(5);
root->right->left = new TreeNode(4);
// 输出从根节点到叶子结点的路径
vector<vector<int>> paths = binaryTreePaths(root);
for (auto path : paths) {
for (auto node : path) {
cout << node << " ";
}
cout << endl;
}
return 0;
}
```
输出结果为:
```
1 2 5
1 3 4
```
其中,每一行都是从根节点到叶子结点的一条路径。
阅读全文