java 在二叉树中寻找最不常见的祖先
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/12056068/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Finding Least Common Ancestor in Binary Tree
提问by Manish
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.
我有一个二叉树，如下所示。我需要找到最不常见的祖先（LCA）。例如，6 和 4 的 LCA 是 1，4 和 5 的 LCA 是 2。
1
/ \
2 3
/ \ / \
4 5 6 7
Can anyone please suggest how should I approach and solve this problem?
谁能建议我应该如何处理和解决这个问题？
回答by slim
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.
现在，调整它以采用两个“目标”参数，target1 和 target2。
When the search for target1 takes you left, and the search for target2 takes you right, you've found the LCA.
当搜索 target1 将您带向左，而搜索 target2 带您向右时，您就找到了 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.
这假设两个目标确实存在。如果您需要断言它们确实如此，则需要在找到潜在的 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;
}
}
回答by Squall
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]
你应该做一个 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;
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.
因为它们都有相同的根祖先。所以你不需要关心不同的深度。你总能找到前（n）个相同的祖先。和祖先（n）是最后的共同祖先。
回答by iloahz
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]，它表示2^j节点的第 -th 个父亲i。我们有
f[i][j] = f[f[i][j - 1]][j - 1]
Now we can get the j-thfather of node i in log(n)time.
现在我们可以及时得到j-th节点 i的父亲了log(n)。
and we need the depth of every node, say h[i]
我们需要每个节点的深度，比如 h[i]
Above can be done in a simple dfs()with complexity of O(N*Log(N)).
以上可以简单地完成dfs()，复杂度为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.
然后对于每个询问节点（i）和节点（j）的 LCA 的查询（i，j），想象两只猴子爬上树，试图到达同一个节点。
- First make them at the same height, then we know they need to get up a same height to meet.
- While they're not at the same node, climb as much as possible.
- The father of the node they are currently at is the LCA.
- 首先让他们处于相同的高度，然后我们知道他们需要站起来相同的高度才能相遇。
- 虽然他们不在同一个节点，但尽可能多地攀登。
- 他们当前所在节点的父节点是 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-thfather of node i, as we mentioned above, which can be
这里的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;
}
so for very query, the complexity is also O(N*Log(N)).
所以对于非常查询，复杂度也是O(N*Log(N))。
