Finding Least Common Ancestor in Binary Tree [dupl

问题:

Possible Duplicate:
How can I find the common ancestor of two nodes in a binary tree?
first common ancestor of a binary tree

I have a binary tree as below. I need to find the least common ancestor (LCA). e.g LCA of 6 and 4 is 1, LCA of 4 and 5 is 2.

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

Can anyone please suggest how should I approach and solve this problem?

回答1:

Start with an ordinary depth-first search algorithm:

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

Now, adapt this to take two "target" parameters, target1 and target2.

When the search for target1 takes you left, and the search for target2 takes you right, you've found the LCA.

This assumes that both targets actually do exist. If you need to assert that they do, you'll need to continue the search after finding the potential 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;
    }
}

回答2:

use a list can solve your problem.

you should make a getAncestorList(). it return a list order by its ancestor eg. 4 has ancestor List [1,2] and 7 has an ancestorList [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;

Because they all have the same root ancestor. so you don't need to care about the different depth. you can always find the top(n) same ancestor. and ancestor(n) is the lastest common ancestor.

回答3:

Here's what I usually do:

first calculate f[i][j], which denotes the 2^j-th father of node i. We have

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

Now we can get the j-th father of node i in log(n) time.

and we need the depth of every node, say h[i]

Above can be done in a simple dfs() with complexity of O(N*Log(N)).

then for every query(i, j) asking the LCA of node(i) and node(j), imagine two monkeys getting up in the tree, trying the get to the same node.

1. First make them at the same height, then we know they need to get up a same height to meet.
2. While they're not at the same node, climb as much as possible.
3. The father of the node they are currently at is the LCA.

you may refer to this:

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

Here getUp(i, j) means find the j-th father of node i, as we mentioned above, which can be

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

so for very query, the complexity is also O(N*Log(N)).