java - 二分木で最も一般的でない祖先を見つける

Question

重複の可能性：
バイナリツリーで2つのノードの共通の祖先を見つけるにはどうすればよいですか？
二分木の最初の共通の祖先

私は以下のような二分木を持っています。最も一般的でない祖先（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);
    }
}

次に、これを2つの「ターゲット」パラメーター、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;

それらはすべて同じルートの祖先を持っているからです。したがって、深さの違いを気にする必要はありません。あなたは常にtop（n）同じ祖先を見つけることができます。ancestor（n）は、最後の共通の祖先です。

Answer 3

これが私が通常行うことです：

最初に計算します。f[i][j]これは、2^jノードの-番目の父を示しますi。我々は持っています

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

j-thこれで、ノードiの父を時間内に取得できますlog(n)。

そして、すべてのノードの深さが必要です。h[i]

dfs()上記は、の複雑さを伴う単純な方法で実行できますO(N*Log(N))。

次に、node（i）とnode（j）のLCAを要求するすべてのquery（i、j）について、2匹のサルがツリーに立ち上がって同じノードに到達しようとしていると想像してください。

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;
}

これは、前述のように、ノードigetUp(i, j)の父親を見つけることを意味します。j-th

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))です。