完全二叉树最近公共祖先算法及C语言实现

算法思路:

为了求出两个结点的最近公共祖先结点，需要先找到它们的共同祖先结点，然后再找到离它们最近的共同祖先结点。

对于一棵完全二叉树，可以通过下标计算出每个结点的父结点的下标。

设当前结点下标为i，则它的父结点下标为i/2（向下取整），它的左子结点下标为2i，右子结点下标为2i+1。

因此，可以从两个结点出发，分别往上找到它们的祖先结点，然后比较祖先结点是否相同，直到找到离它们最近的共同祖先结点为止。

算法实现:

int findLCA(int A[], int n, int i, int j) {
    while (i != j) {
        if (i > j) {
            i /= 2;
        } else {
            j /= 2;
        }
    }
    return i;
}

时间复杂度: 最坏情况下，需要向上找到根结点，因此时间复杂度为O(log n)。

示例:

假设完全二叉树的数组存储方式如下：

int A[] = {1, 2, 3, 4, 5, 6, 7};

则下标为3和6的两个结点的最近公共祖先结点为下标为1的结点，其值为2。

int lca = findLCA(A, 7, 3, 6);
printf("最近公共祖先结点的下标为: %d, 值为: %d\n", lca, A[lca]);

输出结果为：

最近公共祖先结点的下标为: 1, 值为: 2

总结:

本文介绍了在完全二叉树中，如何通过数组存储方式快速找到两个结点的最近公共祖先。该算法简单易懂，时间复杂度为O(log n)，适用于大多数情况。