漫画讲解C语言中最近公共祖先的三种类型

C语言是一种广泛使用的编程语言，它在编程领域中具有重要的地位。C语言中最近公共祖先（Lowest Common Ancestor，LCA）是一个重要的问题，对于许多算法和数据结构来说，它都是必不可少的。在C语言中，最近公共祖先的三种类型分别是二叉树中的最近公共祖先、BST中的最近公共祖先和树中的最近公共祖先。

二叉树中的最近公共祖先

在二叉树中，最近公共祖先（LCA）是指两个节点中最接近它们的公共祖先节点。要求一个二叉树中两个节点的LCA，需要从根节点开始遍历，找到两个节点的路径，然后让它们从最顶端开始向下走，直到它们的路径不同为止。

C语言实现二叉树最近公共祖先的程序如下：

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

struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    if (root == NULL || root == p || root == q) {
        return root;
    }

    struct TreeNode *left = lowestCommonAncestor(root->left, p, q);
    struct TreeNode *right = lowestCommonAncestor(root->right, p, q);

    if (left != NULL && right != NULL) {
        return root;
    } else {
        return left ? left : right;
    }
}

BST中的最近公共祖先

二叉搜索树（Binary Search Tree，BST）是一种特殊的二叉树，其中每个节点的左子树中的值都小于该节点的值，右子树中的值都大于该节点的值。这意味着，对于任何节点p和q，它们的最近公共祖先在树中必须是一个节点的子节点或另一个节点的祖先。

C语言实现BST最近公共祖先的程序如下：

struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    if (root->val > p->val && root->val > q->val) {
        return lowestCommonAncestor(root->left, p, q);
    } else if (root->val < p->val && root->val < q->val) {
        return lowestCommonAncestor(root->right, p, q);
    } else {
        return root;
    }
}

树中的最近公共祖先

在一般情况下，两个节点的LCA可能不在它们的父节点中。这时，我们需要找到两个节点的路径，从根节点出发，找到它们的最近公共祖先。

C语言实现树最近公共祖先的程序如下：

struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    if (root == NULL || root == p || root == q) {
        return root;
    }

    struct TreeNode *left = lowestCommonAncestor(root->left, p, q);
    struct TreeNode *right = lowestCommonAncestor(root->right, p, q);

    if (left != NULL && right != NULL) {
        return root;
    } else {
        return left ? left : right;
    }
}

总结

最近公共祖先是一个重要的问题，它可以用在许多领域例如树的遍历、二叉搜索树、求LCA等等。C语言中最近公共祖先的三种类型分别是二叉树中的最近公共祖先、BST中的最近公共祖先和树中的最近公共祖先。我们可以使用递归算法来解决这些问题。