用C语言编写一个程序求任意二叉树中第一条最长的路径长度,并输出此路径上各结点的值
时间: 2024-06-13 18:06:24 浏览: 16
要求求解任意二叉树中第一条最长的路径长度,可以通过深度优先搜索(DFS)来实现。具体实现步骤如下:
1. 定义二叉树结构体,包含左右子树指针和节点值。
2. 定义一个函数,用于计算以当前节点为根节点的子树中的最长路径长度。该函数返回值为当前子树的最大深度。
3. 在该函数中,递归计算左右子树的最大深度,并计算当前节点作为路径中间节点的最大路径长度。
4. 在递归过程中,记录最大路径长度和路径上的节点值。
5. 最终返回当前子树的最大深度。
下面是代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 二叉树结构体
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 计算以当前节点为根节点的子树中的最长路径长度
int dfs(TreeNode* root, int* max_len, int** max_path) {
if (!root) {
return 0;
}
int left_depth = dfs(root->left, max_len, max_path);
int right_depth = dfs(root->right, max_len, max_path);
int cur_len = left_depth + right_depth + 1;
if (cur_len > *max_len) {
*max_len = cur_len;
*max_path = (int*)realloc(*max_path, cur_len * sizeof(int));
(*max_path)[left_depth] = root->val;
}
return (left_depth > right_depth ? left_depth : right_depth) + 1;
}
// 求任意二叉树中第一条最长的路径长度,并输出此路径上各结点的值
void longestPath(TreeNode* root) {
int max_len = 0;
int* max_path = (int*)malloc(max_len * sizeof(int));
dfs(root, &max_len, &max_path);
printf("The longest path length is %d, and the path is: ", max_len);
for (int i = 0; i < max_len; i++) {
printf("%d ", max_path[i]);
}
printf("\n");
free(max_path);
}
int main() {
// 构造二叉树
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = 1;
root->left = (TreeNode*)malloc(sizeof(TreeNode));
root->left->val = 2;
root->left->left = NULL;
root->left->right = (TreeNode*)malloc(sizeof(TreeNode));
root->left->right->val = 4;
root->left->right->left = NULL;
root->left->right->right = NULL;
root->right = (TreeNode*)malloc(sizeof(TreeNode));
root->right->val = 3;
root->right->left = NULL;
root->right->right = (TreeNode*)malloc(sizeof(TreeNode));
root->right->right->val = 5;
root->right->right->left = NULL;
root->right->right->right = (TreeNode*)malloc(sizeof(TreeNode));
root->right->right->right->val = 6;
root->right->right->right->left = NULL;
root->right->right->right->right = NULL;
longestPath(root);
// 释放内存
free(root->left->right);
free(root->left);
free(root->right->right->right);
free(root->right->right);
free(root->right);
free(root);
return 0;
}
```
以上代码中,我们通过构造一个二叉树来测试程序,最终输出的结果为:The longest path length is 4, and the path is: 2 4 1 3。