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

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

我有一个二叉树如下。 我需要找到最不常见的祖先（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有祖先List [1,2]，7有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; 

因为它们都有相同的根祖先。 所以你不需要关心不同的深度。 你总能找到顶级（同一位）的祖先。 和祖先（n）是最新的共同祖先。

Answer 3

这是我通常做的事情：

首先计算f[i][j] ，其表示节点i第2^j个第2^j个父亲。 我们有

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

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

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

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

然后对于询问节点（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)意味着找到节点i j-th父亲，如上所述，可以是

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

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