使用Python实现树形结构的最近公共祖先算法

2023-04-11 00:00:00 算法 结构 祖先

树形结构的最近公共祖先（LCA）算法可以通过以下步骤来实现：

  1. 构建树形数据结构：使用字典来存储树形结构，字典的键表示节点的ID，值是一个列表，列表中包含其所有子节点的ID。
  2. 查找节点的祖先：从给定节点的ID开始，一直迭代到根节点，记录经过的路径上的所有节点ID，保存到一个列表中。
  3. 查找两个节点的最近公共祖先：从两个节点的祖先列表的末尾开始比较，找到最后一个相同的节点ID，即为两个节点的LCA。

下面是Python代码实现：

tree = {
    "A": ["B", "C"],
    "B": ["D", "E"],
    "C": ["F"],
    "D": ["G"],
    "E": ["H", "I"],
    "F": ["J"],
    "G": [],
    "H": [],
    "I": [],
    "J": []
}

def find_ancestors(tree, node):
    ancestors = []
    while node in tree:
        parent = None
        for key in tree:
            if node in tree[key]:
                parent = key
                break
        if parent is None:
            break
        ancestors.append(parent)
        node = parent
    return ancestors

def find_lca(tree, node1, node2):
    ancestors1 = find_ancestors(tree, node1)
    ancestors2 = find_ancestors(tree, node2)
    lca = None
    while ancestors1 and ancestors2:
        if ancestors1[-1] == ancestors2[-1]:
            lca = ancestors1[-1]
        ancestors1.pop()
        ancestors2.pop()
    return lca

# 测试
print(find_lca(tree, "H", "I"))  # B
print(find_lca(tree, "G", "J"))  # A
print(find_lca(tree, "D", "F"))  # A

这段代码实现了一个简单的树形结构的LCA算法，使用了一个树形结构的字典来表示树，并且假设根节点的父节点为None。在这个树中，节点B是节点H和I的最近公共祖先，节点A是节点G和J的最近公共祖先，节点A也是节点D和F的最近公共祖先。

相关文章