使用C语言求二叉树结点的最低公共祖先的方法

当我们需要寻找二叉树中两个结点的最近公共祖先时，可以使用C语言实现一种基于递归的算法来解决这个问题。具体的方法为：

算法思路

1. 从根结点开始遍历二叉树，如果当前结点是NULL，则直接返回NULL；
2. 如果当前结点等于其中任意一个目标结点，则直接返回这个结点；
3. 如果没有找到目标结点，则分别在其左右子树中递归查找；
4. 如果左右子树均找到了目标结点，则当前结点即为它们的最近公共祖先；
5. 如果左右子树只有一个找到了目标结点，则递归查找另一个目标结点；
6. 如果左右子树都没有找到目标结点，则返回NULL。

代码示例

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 if (left != NULL) return left;
    else if (right != NULL) return right;
    else return NULL;
}

示例说明

假设有下面这棵二叉树：

        1
       / \
      2   3
     / \ / \
    4  5 6  7

我们需要求出结点4和结点5的最近公共祖先，这里我们将以上述代码为例，进行解释：

首先，从根结点1开始遍历。

然后分别去左右子树中递归查找目标结点4和5，由于它们分别在左右子树中，因此最近公共祖先即为当前结点2。

最终返回结点2即可。

再假设我们需要求出结点6和结点7的最近公共祖先。

根据代码，我们可以发现它们分别在右子树中，而左子树中没有目标结点，因此需要继续递归查找。

由于结点6和结点7是对称的，因此可以将左子树看成右子树，右子树看成左子树，这样的话问题就变成了求结点2和结点3的最近公共祖先。

继续递归查找之后，发现最近公共祖先为根结点1。

最终返回结点1即可。