C语言求任意二叉树中第一条最长的路径长度,并输出此路径上各结点的值。
时间: 2023-06-25 21:06:07 浏览: 201
这道题可以用递归的方式来解决,具体思路如下:
1. 如果二叉树为空,直接返回0。
2. 分别计算左右子树的最大深度maxDepth和左右子树中的最长路径长度,分别为leftPath和rightPath。
3. 比较leftPath + rightPath和当前最长路径长度maxLength,如果大于maxLength,则更新maxLength,并记录当前路径上的结点值。
4. 最终返回maxDepth和maxLength中的较大值作为当前子树的最大深度。
下面是对应的C语言代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 二叉树结点定义
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
void findLongestPath(struct TreeNode* root, int* maxLength, int** path, int* pathIndex) {
if (!root) {
return;
}
int leftDepth = findLongestPath(root->left, maxLength, path, pathIndex);
int rightDepth = findLongestPath(root->right, maxLength, path, pathIndex);
int leftPath = 0;
if (root->left && root->left->val == root->val) {
leftPath = leftDepth + 1;
}
int rightPath = 0;
if (root->right && root->right->val == root->val) {
rightPath = rightDepth + 1;
}
int currentPath = leftPath + rightPath;
if (currentPath > *maxLength) {
*maxLength = currentPath;
*pathIndex = 0;
(*path)[(*pathIndex)++] = root->val;
} else if (currentPath == *maxLength) {
(*path)[(*pathIndex)++] = root->val;
}
return 1 + (leftDepth > rightDepth ? leftDepth : rightDepth);
}
int* longestUnivaluePath(struct TreeNode* root, int* returnSize) {
int maxLength = 0;
int* path = (int*)malloc(sizeof(int) * 1000);
int pathIndex = 0;
findLongestPath(root, &maxLength, &path, &pathIndex);
*returnSize = pathIndex;
return path;
}
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 = 4;
root->left->left = NULL;
root->left->right = NULL;
root->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->right->val = 5;
root->right->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->right->left->val = 5;
root->right->left->left = NULL;
root->right->left->right = 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 returnSize;
int* path = longestUnivaluePath(root, &returnSize);
printf("The longest path length is: %d\n", returnSize);
printf("The values on the path are: ");
for (int i = 0; i < returnSize; i++) {
printf("%d ", path[i]);
}
printf("\n");
free(path);
free(root->left);
free(root->right->left);
free(root->right->right);
free(root);
return 0;
}
```
注:此代码中的二叉树是固定的,实际使用时需要根据题目要求构造对应的二叉树。
阅读全文