编写函数void longestPath(BiTNode *T), 求二叉树T中第一条最长的路径长度,并输出此路径上各结点的值
时间: 2024-02-13 13:02:23 浏览: 24
以下是实现代码:
```c++
#include <iostream>
#include <vector>
using namespace std;
struct BiTNode {
int val;
BiTNode *left;
BiTNode *right;
BiTNode(int x) : val(x), left(NULL), right(NULL) {}
};
void dfs(BiTNode *root, vector<int> &path, int &maxLen, vector<int> &maxPath) {
if (!root) return;
path.push_back(root->val);
if (!root->left && !root->right) { // 叶子节点
if (path.size() > maxLen) {
maxLen = path.size();
maxPath = path;
}
}
dfs(root->left, path, maxLen, maxPath);
dfs(root->right, path, maxLen, maxPath);
path.pop_back();
}
void longestPath(BiTNode *T) {
if (!T) return;
vector<int> path, maxPath;
int maxLen = 0;
dfs(T, path, maxLen, maxPath);
cout << "The length of the longest path is " << maxLen << endl;
cout << "The nodes on the path are: ";
for (int i = 0; i < maxPath.size(); i++) {
cout << maxPath[i] << " ";
}
}
int main() {
BiTNode *root = new BiTNode(1);
root->left = new BiTNode(2);
root->right = new BiTNode(3);
root->left->left = new BiTNode(4);
root->left->right = new BiTNode(5);
root->right->left = new BiTNode(6);
root->right->right = new BiTNode(7);
longestPath(root);
return 0;
}
```
函数`dfs`是用来进行递归遍历二叉树的,`path`保存了当前遍历路径上的节点值,`maxLen`和`maxPath`分别记录最长路径的长度和节点值。当遍历到叶子节点时,如果当前路径的长度大于`maxLen`,则更新`maxLen`和`maxPath`。
函数`longestPath`是主函数,先判断根节点是否为空,然后调用`dfs`进行遍历,并输出最长路径的长度和节点值。
此函数的时间复杂度是O(N),其中N为二叉树的节点数,因为需要遍历所有节点。