java - 在二叉树中寻找最小共同祖先

Question

可能重复：
如何在二叉树中找到两个节点的共同祖先？
二叉树的第一个共同祖先

我有一个如下的二叉树。我需要找到最小共同祖先（LCA）。例如，6 和 4 的 LCA 为 1，4 和 5 的 LCA 为 2。

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

谁能建议我应该如何处理和解决这个问题？

Answer 1

从一个普通的深度优先搜索算法开始：

public Node find(Node node, int target) {
    if(node == null || node.value == target) {
        return node;
    }
    if(node.value > target) {
        return find(node.left, target);
    } else {
        return find(node.right, target);
    }
}

现在，调整它以采用两个“目标”参数，target1 和 target2。

当对 target1 的搜索将您带到左侧，而对 target2 的搜索将您带到右侧时，您就找到了 LCA。

这假设两个目标都确实存在。如果您需要断言他们这样做，您需要在找到潜在的 LCA 后继续搜索。

public Node findLca(Node node, int t1, int t2) {
    if(node == null) {
        return null;
    }
    if(node.value > t2 && node.value > t1) {
        // both targets are left
        return findLca(node.left, t1, t2);
    } else if (node.value < t2 && node.value < t1) {
        // both targets are right
        return findLca(node.right, t1, t2);
    } else {
        // either we are diverging or both targets are equal
        // in both cases so we've found the LCA
        // check for actual existence of targets here, if you like
        return node;
    }
}

Answer 2

使用列表可以解决您的问题。

你应该做一个 getAncestorList()。它按其祖先返回列表顺序，例如。4 有祖先列表 [1,2] 和 7 有祖先列表 [1,3]

list1 = node1.getAncestorList()
list2 = node2.getAncestorList()

minlength = min(list1.size(), list2.size())
for (int i = 0; i < minlength; i++) {
    e1 = list1.getItemAt(i);
    e2 = list2.getItemAt(i);
    if (e1 == e2) ec = e1;
}
return ec;

因为它们都有相同的根祖先。所以你不需要关心不同的深度。你总能找到前（n）个相同的祖先。祖先（n）是最近的共同祖先。

Answer 3

这是我通常做的：

first calculate f[i][j]，表示2^jnode 的第 -th 个父亲i。我们有

f[i][j] = f[f[i][j - 1]][j - 1]

现在我们可以及时得到j-th节点 i 的父亲log(n)。

我们需要每个节点的深度，比如说h[i]

以上可以用简单dfs()的复杂度来完成O(N*Log(N))。

然后对于每个查询节点（i）和节点（j）的 LCA 的查询（i，j），想象有两只猴子在树上爬起来，试图到达同一个节点。

1. 首先使它们处于相同的高度，然后我们知道它们需要起床相同的高度才能相遇。
2. 虽然他们不在同一个节点，但尽可能地攀登。
3. 他们当前所在节点的父亲是 LCA。

你可以参考这个：

int query(int u, int v){
    if(h[u]>h[v])swap(u,v);
    v = getUp(v,h[v]-h[u]);
    for(int i=log(n);i>=0;i--){
        if(f[u][i]!=f[v][i]){
            u=f[u][i];
            v=f[v][i];
        }
    }
    while(u!=v){
        u=f[u][0];
        v=f[v][0];
    }
    return u;
}

这里getUp(i, j)的意思是找到j-th节点i的父亲，正如我们上面提到的，可以是

int nt(int u,int x){
    for(int i=log(n);i>=0;i--){
        if((1<<i)<=x){
            u=f[u][i];
            x-=(1<<i);
        }
    }
    return u;
}

所以对于非常查询，复杂度也是O(N*Log(N))。