二叉树的最近公共祖先 c語言

二叉树的最近公共祖先（Lowest Common Ancestor，LCA）是指一棵给定的二叉树中两个节点之间的最短路径上共同的祖先节点。在二叉树中查找LCA通常通过递归的方式来解决。以下是使用C语言的一种常见算法：

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

// 定义辅助函数，返回根节点、左子树的LCA或右子树的LCA
int lcaHelper(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    if (!root || root == p || root == q) {
        return root; // 如果根为空，或者p或q等于当前根，那么根就是LCA
    }
    
    // 分别递归查询左子树和右子树的LCA
    struct TreeNode* left = lcaHelper(root->left, p, q);
    struct TreeNode* right = lcaHelper(root->right, p, q);

    // 如果左右子树的LCA不相等，说明根就是LCA
    if (left && right && left != right)
        return root;
    else
        return left ? left : right; // 否则返回其中一个子树的LCA
}

// 主函数，输入二叉树的根节点以及两个需要查找LCA的节点
struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    return lcaHelper(root, p, q);
}