求任意二叉树中第一条最长的路径长度,并输出此路径上各结点的值用c语言编写
时间: 2024-06-13 07:06:31 浏览: 90
以下是求任意二叉树中第一条最长的路径长度,并输出此路径上各结点的值的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
int maxDepth(struct TreeNode* root) {
if (root == NULL) {
return 0;
}
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
void findLongestPath(struct TreeNode* root, int* maxLen, int* path, int* curLen) {
if (root == NULL) {
return;
}
path[(*curLen)++] = root->val;
if (root->left == NULL && root->right == NULL) {
if (*curLen > *maxLen) {
*maxLen = *curLen;
for (int i = 0; i < *curLen; i++) {
printf("%d ", path[i]);
}
printf("\n");
}
} else {
findLongestPath(root->left, maxLen, path, curLen);
findLongestPath(root->right, maxLen, path, curLen);
}
(*curLen)--;
}
int longestPath(struct TreeNode* root) {
int maxLen = 0;
int path[1000];
int curLen = 0;
findLongestPath(root, &maxLen, path, &curLen);
return maxLen;
}
int main() {
// 构造二叉树
struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->val = 1;
root->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->left->val = 2;
root->left->left = NULL;
root->left->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->left->right->val = 4;
root->left->right->left = NULL;
root->left->right->right = NULL;
root->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->right->val = 3;
root->right->left = NULL;
root->right->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->right->right->val = 5;
root->right->right->left = NULL;
root->right->right->right = NULL;
// 求最长路径长度并输出路径
int maxLen = longestPath(root);
printf("The length of the longest path is: %d\n", maxLen);
return 0;
}
```
阅读全文