用c求二叉树中第一条最长的路径长度,并输出此路径上各结点。
时间: 2023-12-10 09:39:00 浏览: 184
以下是用C语言求解二叉树中第一条最长路径长度并输出的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树结点结构体
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 定义全局变量,保存最大路径长度和路径上的结点
int max_len = 0;
TreeNode* max_path[100];
// 求解二叉树中第一条最长路径长度
void dfs(TreeNode* root, int depth, TreeNode** path) {
if (root == NULL) return;
path[depth] = root;
if (root->left == NULL && root->right == NULL) {
if (depth > max_len) {
max_len = depth;
for (int i = 0; i <= depth; i++) {
max_path[i] = path[i];
}
}
}
dfs(root->left, depth + 1, path);
dfs(root->right, depth + 1, path);
}
// 输出路径上的结点
void printPath(TreeNode** path, int len) {
for (int i = 0; i < len; i++) {
printf("%d ", path[i]->val);
}
printf("\n");
}
int main() {
// 构建二叉树
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = 1;
TreeNode* node2 = (TreeNode*)malloc(sizeof(TreeNode));
node2->val = 2;
TreeNode* node3 = (TreeNode*)malloc(sizeof(TreeNode));
node3->val = 3;
TreeNode* node4 = (TreeNode*)malloc(sizeof(TreeNode));
node4->val = 4;
TreeNode* node5 = (TreeNode*)malloc(sizeof(TreeNode));
node5->val = 5;
root->left = node2;
root->right = node3;
node2->left = node4;
node2->right = NULL;
node3->left = NULL;
node3->right = node5;
node4->left = NULL;
node4->right = NULL;
node5->left = NULL;
node5->right = NULL;
// 求解最长路径
TreeNode* path[100];
dfs(root, 0, path);
// 输出结果
printf("Max length: %d\n", max_len);
printf("Max path: ");
printPath(max_path, max_len + 1);
return 0;
}
```
以上代码中,我们使用深度优先搜索(DFS)遍历二叉树,记录当前路径上的结点,并在遍历到叶子结点时判断当前路径长度是否大于最大路径长度,如果是则更新最大路径长度和路径上的结点。最后输出最大路径长度和路径上的结点即可。
阅读全文