标签: lowest-common-ancestor

想象一下有向无环图如下,其中:

• "A"是根(总有一个根)
• 每个节点都知道它的父节点
• 节点名称是任意的 - 没有什么可以从它们推断出来
• 我们从另一个来源得知节点是按照A到G的顺序添加到树中的(例如它们是版本控制系统中的提交)

我可以使用什么算法来确定两个任意节点的最低共同祖先(LCA),例如,共同的祖先:

• B和E是B.
• D和F是B.

注意:

• 从根开始到给定节点不一定有一条路径(例如"G"有两条路径),因此您不能简单地遍历从根到两个节点的路径并查找最后一个相等的元素
• 我发现树的LCA算法,特别是二叉树,但它们不适用于此,因为一个节点可以有多个父节点(即这不是一棵树)

我遇到了以下实现并花了一些时间,但仍然无法掌握这个想法.有人可以逐行解释它在做什么吗？我只是不明白在什么时候它可以决定一个节点是一个祖先.

谢谢

public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q)  return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left != null && right != null)   return root;
        return left != null ? left : right;
    }
}

我正在尝试为无根树实施LCA.我已经给出了一个树(一个没有循环的连通无向图)和一些关于某些根和两个顶点的LCA的查询.每个特定的查询都可以有不同的根,所以我不能使用在开始时对任意根进行预处理的算法.

到目前为止,我已经尝试使用DFS找到从顶点到根的路径,然后检查它在哪里发散,但是它有点慢(O(nq),其中q是查询数).

有任何建议如何预处理树,以便具有查询的次线性复杂性？

使用NetworkX

我希望从DiGraph中的node1和node11获得最低的共同祖先.

以下是代码.

import networkx as nx

G = nx.DiGraph() #Directed graph
G.add_nodes_from([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15])
G.add_edges_from([(2,1),(3,1),(4,1),(5,2),(6,2),(7,3),(8,3),(9,3),(10,4),(10,12),(14,9),(15,8),(12,11),(13,11),(14,12),(15,13)])

ancestors1 = nx.ancestors(G, 1)
ancestors2 = nx.ancestors(G, 11)

src_set = set(ancestors1)
tag_set = set(ancestors2)
matched_list = list(src_set & tag_set)

dic = {}

for elem in matched_list:
    print elem
    length1 = nx.dijkstra_path_length(G, elem, 1)
    path1 = nx.dijkstra_path(G, elem, 1)
    dist1 = len(path1)
    length2 = nx.dijkstra_path_length(G, elem, 11)
    path2 = nx.dijkstra_path(G, elem, 11)
    dist2 = len(path2)
    dist_sum = dist1 + dist2
    dic[elem] = dist_sum

min_num = min(dic.values()) 
for …

我正在考虑这个挑战：

给定具有N 个节点和N-1 条边的树。树上的每条边都用拉丁字母表中的一串小写字母标记。给定Q查询，由两个节点u和v 组成，检查是否可以创建一个回文字符串，该字符串使用属于从节点u到节点v的路径中边上标记的字符串的所有字符。

字符可以按任何顺序使用。

N是 10 ^{5 的数量级}，Q是 10 ^{6 的数量级}

输入：

N=3
u=1 v=3 重量=bc
u=1 v=2 重量=aba
Q=4
u=1 v=2
u=2 v=3
u=3 v=1
u=3 v=3

输出：

是
是
否
否

我的想法是使用稀疏表和欧拉塔上的范围最小查询通过O(1) 中的预计算来计算 2 个节点之间的 LCA ，然后查看从 LCA 到节点 u 和 LCA 到节点 v 的路径并存储所有字符频率。如果所有字符的频率之和为奇数，我们检查除一个字符外的每个字符的频率是否为奇数。如果所有字符的频率总和是偶数，我们检查每个字符的频率是否是偶数。但是这个过程肯定会超时，因为Q可以达到 10 ⁶。

有人有更好的算法吗？