如何使用Python实现链表的二叉树的最近公共祖先（Lowest Common Ancestor of a Binary Tree）操作

2023-04-11 00:00:00 链表如何使用祖先

这里提供一个实现链表的二叉树最近公共祖先的Python代码。

我们先定义一个节点类：

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

接下来，我们用一个字典来存储每个节点的父节点，方便我们向上查找祖先节点：

parent = {root: None}
def dfs(node):
    if node.left:
        parent[node.left] = node
        dfs(node.left)
    if node.right:
        parent[node.right] = node
        dfs(node.right)
dfs(root)

然后，我们定义一个函数来找到两个节点的最近公共祖先：

def lowestCommonAncestor(p, q):
    ancestors = set()
    while p:
        ancestors.add(p)
        p = parent[p]
    while q not in ancestors:
        q = parent[q]
    return q

这个函数先从p节点向上查找所有祖先节点，并将其加入一个集合中。然后从q节点向上查找，直到找到第一个出现在祖先集合中的节点即为最近公共祖先。

完整代码如下：

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def lowestCommonAncestor(p, q):
    ancestors = set()
    while p:
        ancestors.add(p)
        p = parent[p]
    while q not in ancestors:
        q = parent[q]
    return q

parent = {root: None}
def dfs(node):
    if node.left:
        parent[node.left] = node
        dfs(node.left)
    if node.right:
        parent[node.right] = node
        dfs(node.right)
dfs(root)

p = Node("pidancode.com")
q = Node("皮蛋编程")
print(lowestCommonAncestor(p, q).val)

注：以上代码仅为示例，需要在实际情况中根据链表二叉树的定义调整相关部分才能使用。

相关文章