运用栈 求二叉树T中第一条最长的路径长度,并输出此路径上各结点的值 c++
时间: 2024-02-13 15:02:45 浏览: 21
以下是C++代码实现,同样使用深度优先搜索(DFS)和栈来实现:
```c++
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
pair<int, vector<int>> dfs(TreeNode* root) {
stack<pair<TreeNode*, vector<int>>> s;
int max_len = 0;
vector<int> max_path;
s.push({root, {root->val}});
while (!s.empty()) {
auto [node, path] = s.top();
s.pop();
if (!node->left && !node->right) { // 叶子节点
if (path.size() > max_len) {
max_len = path.size();
max_path = path;
}
}
if (node->left && find(path.begin(), path.end(), node->left->val) == path.end()) {
vector<int> new_path = path;
new_path.push_back(node->left->val);
s.push({node->left, new_path});
}
if (node->right && find(path.begin(), path.end(), node->right->val) == path.end()) {
vector<int> new_path = path;
new_path.push_back(node->right->val);
s.push({node->right, new_path});
}
}
return {max_len, max_path};
}
int main() {
// 示例二叉树
// 1
// / \
// 2 3
// / \ \
// 4 5 6
// / \
// 7 8
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);
root->right->right = new TreeNode(6);
root->right->right->left = new TreeNode(7);
root->right->right->right = new TreeNode(8);
auto [max_len, max_path] = dfs(root);
cout << "最长路径长度为:" << max_len << endl;
cout << "路径上的节点值为:";
for (int val : max_path) {
cout << val << " ";
}
cout << endl;
return 0;
}
```
输出结果为:
```
最长路径长度为:5
路径上的节点值为:1 3 6 8 7
```