用c语言写一个代码,借助栈来实现,用后序遍历求二叉树第一条最长的路径,并输出此路径各节点的值
时间: 2024-10-01 19:03:30 浏览: 22
在C语言中,我们可以使用递归和栈来实现后序遍历二叉树,并找到最长路径。由于栈的数据结构特性(LIFO,即最后进栈的元素最先出栈),我们可以在访问每个节点的同时,记录当前路径的长度以及路径上的节点值。
下面是一个简单的C代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点结构体
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 判断是否为空
int isEmpty(TreeNode* node) {
return !node;
}
// 助手函数,将路径加入结果数组
void appendPath(int path[], int index, int sum, TreeNode* node, int** result, int* maxLen) {
if (isEmpty(node)) return;
// 后续处理节点
appendPath(path, ++index, sum + node->val, node->left, result, maxLen);
appendPath(path, index, sum + node->val, node->right, result, maxLen);
// 更新最长路径
if (sum + node->val > (*maxLen) && (!isEmpty(node->left) || !isEmpty(node->right))) {
*maxLen = sum + node->val;
for (int i = index; i <= *maxLen; ++i) {
(*result)[i] = node->val;
}
}
}
// 主函数:后序遍历并查找最长路径
int* findLongestPath(TreeNode* root) {
int maxLen = 0;
int* longestPath = malloc(sizeof(int) * (root == NULL ? 0 : maxLen + 1));
longestPath[0] = 0; // 初始化路径
stack<TreeNode*> s;
s.push(root);
while (!s.isEmpty()) {
TreeNode* node = s.top();
s.pop();
if (isEmpty(node)) continue;
appendPath(longestPath, 0, node->val, node, &longestPath, &maxLen);
// 将左右子节点压入栈
s.push(node->left);
s.push(node->right);
}
return longestPath;
}
// 示例用法
int main() {
// 创建一个二叉树实例
// ...
TreeNode* root = ...;
int* path = findLongestPath(root);
printf("最长路径值为: ");
for (int i = 0; i < (root == NULL ? 0 : maxLen); ++i) {
printf("%d ", path[i]);
}
printf("\n");
free(path);
return 0;
}
```
在这个代码中,`findLongestPath` 函数负责整个过程,它首先初始化最长路径数组、栈,然后按照后序遍历的方式处理节点。如果遇到一条比当前最长路径更长的路径,就更新最长路径及其对应的节点值。
请注意,你需要自定义创建二叉树的函数或者实例化数据结构以便在main函数中使用。此外,记得释放动态分配的内存以避免内存泄漏。
阅读全文