使用cpp语言实现得到二叉树的所有叶子结点到根结点的路径及路径长度,写出可直接运行的代码
时间: 2023-05-31 18:07:17 浏览: 93
二叉树遍历 非递归 C++实现代码
5星 · 资源好评率100%
好的,以下是可直接运行的 C++ 代码:
```cpp
#include <iostream>
#include <vector>
using namespace std;
// 二叉树节点的结构体
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 获取二叉树的所有叶子节点到根节点的路径及路径长度
void dfs(TreeNode* root, vector<int>& path, vector<vector<int>>& res) {
if (!root) {
return;
}
path.push_back(root->val); // 当前节点加入路径
if (!root->left && !root->right) { // 当前节点为叶子节点,加入到结果
res.push_back(path);
} else {
dfs(root->left, path, res); // 往左子树递归
dfs(root->right, path, res); // 往右子树递归
}
path.pop_back(); // 递归完成后移除当前节点
}
// 主函数
int main() {
// 构建一个二叉树
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
// 获取所有叶子节点到根节点的路径
vector<vector<int>> res;
vector<int> path;
dfs(root, path, res);
// 输出结果
for (auto p : res) {
cout << "Path: ";
for (int i = p.size() - 1; i >= 0; i--) { // 从叶子节点到根节点
cout << p[i] << " ";
}
cout << " | Length: " << p.size() - 1 << endl;
}
return 0;
}
```
该代码使用深度优先搜索(DFS)算法,时间复杂度为 O(N),N 是二叉树的节点数。其中,res 存储所有叶子节点到根节点的路径,path 存储当前递归路径,p.size()-1 即为路径长度。
阅读全文