C语言LCA算法详解（手把手教你实现最近公共祖先算法）

什么是LCA？

给定一棵有根树（通常为二叉树），以及树中的两个节点 u 和 v，它们的最近公共祖先是指离根最远的、同时是 u 和 v 祖先的节点。

例如，在下图中，节点 4 和 5 的 LCA 是节点 2；节点 4 和 6 的 LCA 是节点 1。

实现思路

我们采用一种简单但高效的递归方法来实现 最近公共祖先算法。该方法适用于二叉树，时间复杂度为 O(n)，其中 n 是树中节点的数量。

基本思想如下：

• 如果当前节点为空，返回 NULL。
• 如果当前节点是 u 或 v，直接返回当前节点。
• 递归查找左子树和右子树。
• 如果左右子树都找到了目标节点，说明当前节点就是 LCA。
• 否则，返回非空的那一侧结果。

C语言代码实现

首先，我们定义二叉树的节点结构：

struct TreeNode {    int val;    struct TreeNode* left;    struct TreeNode* right;};

接下来是核心的 LCA 函数实现：

struct TreeNode* findLCA(struct TreeNode* root,                          struct TreeNode* p,                          struct TreeNode* q) {    // 如果根为空，或者 p/q 其中一个是根，则返回根    if (root == NULL || root == p || root == q) {        return root;    }    // 递归查找左右子树    struct TreeNode* left = findLCA(root->left, p, q);    struct TreeNode* right = findLCA(root->right, p, q);    // 如果左右子树都找到了，说明当前节点是 LCA    if (left != NULL && right != NULL) {        return root;    }    // 否则返回非空的一边    return (left != NULL) ? left : right;}

完整示例程序

下面是一个完整的可运行示例，包含节点创建和测试：

#include <stdio.h>#include <stdlib.h>struct TreeNode {    int val;    struct TreeNode* left;    struct TreeNode* right;};struct TreeNode* createNode(int val) {    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));    node->val = val;    node->left = NULL;    node->right = NULL;    return node;}struct TreeNode* findLCA(struct TreeNode* root,                          struct TreeNode* p,                          struct TreeNode* q) {    if (root == NULL || root == p || root == q) {        return root;    }    struct TreeNode* left = findLCA(root->left, p, q);    struct TreeNode* right = findLCA(root->right, p, q);    if (left && right) {        return root;    }    return left ? left : right;}int main() {    // 构建如下二叉树：    //       1    //      / \    //     2   3    //    / \    //   4   5    struct TreeNode* root = createNode(1);    root->left = createNode(2);    root->right = createNode(3);    root->left->left = createNode(4);    root->left->right = createNode(5);    struct TreeNode* p = root->left->left; // 节点 4    struct TreeNode* q = root->left->right; // 节点 5    struct TreeNode* lca = findLCA(root, p, q);    if (lca != NULL) {        printf("LCA of %d and %d is %d\n", p->val, q->val, lca->val);    } else {        printf("LCA not found.\n");    }    // 释放内存（简化处理，实际应递归释放）    free(root->left->left);    free(root->left->right);    free(root->left);    free(root->right);    free(root);    return 0;}

总结

通过本教程，你已经掌握了如何用 C语言实现LCA算法。这种递归方法简洁高效，非常适合初学者理解和应用。掌握 C语言树结构 的操作是学习更高级数据结构（如线段树、Trie 树等）的基础。

如果你正在准备算法面试或学习数据结构课程，LCA算法实现 是一个非常值得掌握的技能点。希望本文能帮助你轻松入门！

记得多动手写代码，加深理解。祝你编程愉快！