c语言求二叉树输出最长路径上的结点
时间: 2024-01-21 07:19:56 浏览: 91
求二叉树的一条最长路径
这里给出一个基于递归的实现。对于一个二叉树,其最长路径可以通过求其左右子树的最大深度之和再加 1(因为要包括根结点)来得到。因此,我们可以递归地求解左右子树的最大深度,然后比较它们的和与当前最长路径长度的大小,如果更大,则更新最长路径长度,并记录下当前根结点。我们可以在递归函数中传递一个指向当前最长路径结点的指针,这样就可以在递归过程中更新最长路径结点。
下面是代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
int maxDepth(TreeNode* root) {
if (root == NULL) {
return 0;
}
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
}
void findLongestPath(TreeNode* root, int* maxLen, TreeNode** maxNode) {
if (root == NULL) {
return;
}
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
int currLen = leftDepth + rightDepth + 1;
if (currLen > *maxLen) {
*maxLen = currLen;
*maxNode = root;
}
findLongestPath(root->left, maxLen, maxNode);
findLongestPath(root->right, maxLen, maxNode);
}
int main() {
// 构造一棵二叉树
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = 1;
root->left = (TreeNode*)malloc(sizeof(TreeNode));
root->left->val = 2;
root->left->left = (TreeNode*)malloc(sizeof(TreeNode));
root->left->left->val = 4;
root->left->left->left = NULL;
root->left->left->right = NULL;
root->left->right = (TreeNode*)malloc(sizeof(TreeNode));
root->left->right->val = 5;
root->left->right->left = (TreeNode*)malloc(sizeof(TreeNode));
root->left->right->left->val = 7;
root->left->right->left->left = NULL;
root->left->right->left->right = 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 = 6;
root->right->right->left = NULL;
root->right->right->right = NULL;
// 找出最长路径结点
int maxLen = 0;
TreeNode* maxNode = NULL;
findLongestPath(root, &maxLen, &maxNode);
// 输出结果
printf("The longest path has length %d, and the node value is %d.\n", maxLen, maxNode->val);
return 0;
}
```
在上面的代码中,我们首先构造了一个二叉树,然后调用 `findLongestPath` 函数找出最长路径结点,最后输出结果。注意,在实际使用中,我们需要对二叉树的结点进行动态分配和释放,以免出现内存泄漏。
阅读全文