假设非空二叉树采用顺序存储结构，每个结点值为单个字符。设计一个算法求编号为i和j的两个结点的最近公共祖先，如果没有则返回0。

### 回答1：
由于二叉树采用顺序存储结构，我们可以通过数组下标来表示每个结点。假设根结点的下标为1，则对于任意一个结点i，它的左子结点下标为2i，右子结点下标为2i+1。

我们可以先找到i和j的路径，然后从根结点开始比较两条路径，找到最后一个相同的结点即为它们的最近公共祖先。

具体算法如下：

1. 定义一个数组path_i，记录结点i的路径，从i开始一直到根结点。同样定义一个数组path_j，记录结点j的路径。

2. 从i开始，依次将i的父结点加入path_i数组，直到根结点。同样从j开始，依次将j的父结点加入path_j数组，直到根结点。

3. 从根结点开始，比较path_i和path_j数组，找到最后一个相同的结点即为它们的最近公共祖先。

具体实现可以参考下面的代码：

int findLCA(char tree[], int n, int i, int j) {
int path_i[n], path_j[n];
int k = i, l = j;
int len_i = , len_j = ;
while (k > 1) {
path_i[len_i++] = k;
k /= 2;
}
while (l > 1) {
path_j[len_j++] = l;
l /= 2;
}
path_i[len_i++] = 1;
path_j[len_j++] = 1;
int m = len_i - 1, n = len_j - 1;
while (m >= && n >= && path_i[m] == path_j[n]) {
m--;
n--;
}
if (m < || n < ) {
return ;
} else {
return path_i[m+1];
}
}

其中，tree是存储二叉树的数组，n是结点个数，i和j是要查找的结点编号。函数返回i和j的最近公共祖先的编号，如果没有则返回。

### 回答2：
先了解一下顺序存储结构吧。在顺序存储结构中，二叉树中的节点按照完全二叉树的形式排列，并按层次顺序从上至下、从左至右依次存储在一段物理地址连续的存储单元中。由于完全二叉树的特殊性质，顺序存储结构可以不使用指针就能方便地实现了二叉树的基本操作。

那么对于这个题，我们可以用一下的思路：

1. 判断i和j结点是否存在。
2. 找到其公共的父节点。
3. 循环上一层找到其公共的父节点，直到找到根节点或则i，j本身就是父子关系。

1. 判断i和j结点是否存在

我们可以根据二叉树的性质，算出最后一个非空节点的编号 n 和 i、j 的编号比较一下。如果 i 或 j 超过了节点数的上限 n ，说明该节点不存在于二叉树中，直接返回 0 。

2. 找到两个结点的公共父节点

我们从根节点开始循环遍历顺序数组。并找到两个结点的父节点，我们可以通过节点编号算出它的父节点编号，父节点编号为 (i - 1) / 2。如果两个节点的父节点编号值相等，则说明两个节点在同一层。此时我们记录下当前父节点的编号，并将 i 和 j 分别迭代到其父节点的位置。

3. 查找整个树的公共祖先

我们重复步骤 2 直到找到整个树的公共祖先。也就是说，每一次循环都将记录下的父节点编号作为起始编号，重复步骤 2 直到找到所有公共的父节点，将这些公共的父节点保存在列表中，最后从列表末尾开始往前查找，查找到的第一个节点就是最近公共祖先，返回该节点编号即可。

算法的大致框架如下：

// 假设 nodes 是顺序表存储的二叉树节点
int findLCA(int i, int j, int n, int nodes[]) {
    if (i > n || j > n) {
        return 0; // 不存在，直接返回0
    }
    vector<int> parents_i, parents_j;
    int p_i = i, p_j = j;
    while (p_i != 0) {
        parents_i.push_back((p_i - 1) / 2);
        p_i = (p_i - 1) / 2;
    }
    while (p_j != 0) {
        parents_j.push_back((p_j - 1) / 2);
        p_j = (p_j - 1) / 2;
    }
    int n1 = parents_i.size(), n2 = parents_j.size();
    int k = min(n1, n2);
    int last = 0;
    for (int t = 0; t < k; t++) {
        if (parents_i[n1 - t - 1] != parents_j[n2 - t - 1]) {
            break;
        }
        last = parents_i[n1 - t - 1];
    }
    if (last == 0) {
        return 0;
    }
    for (int t = k; t < n1; t++) {
        if (parents_i[n1 - t - 1] == last) {
            last = parents_i[n1 - t - 1];
        } else {
            break;
        }
    }
    return last;
}

以上就是这个问题的全部解答，希望对你有所帮助。

### 回答3：
顺序存储二叉树是指将二叉树的节点按照从上到下，从左到右的顺序依次存储在一个数组中，利用这种存储方式，可以通过其下标计算出一个节点的父节点、左子节点和右子节点。

对于这个问题，可以利用以下步骤设计算法：

1. 如果i或j等于0，则返回0。
2. 根据节点下标计算出i和j的父节点p和q，这里可以用一个公式计算出节点的父节点：(i-1)/2，(j-1)/2。
3. 如果p等于q，则p（或q）就是最近公共祖先，返回p（或q）。
4. 如果p不等于q，则将p和q都向其父节点移动一层，重复步骤3和4，直到找到它们的最近公共祖先为止。

可以看出这个算法的时间复杂度取决于节点所在树的高度，最坏情况下需要遍历整棵树，时间复杂度为O(n)，因此这种算法不适用于高度很大的二叉树。