使用Python查找二叉树的最近公共祖先的程序

二叉树是一种经典的树状数据结构，其中每个节点最多有两个子节点。在一个二叉树中，我们可以通过查找节点的父节点，找到它的所有祖先。在使用二叉树时，问题常常是需要查找两个节点的最近公共祖先，即它们最靠近的共同祖先节点。在这篇文章中，我们将探讨使用Python实现查找二叉树最近公共祖先的方法。

更多Python相关文章，请阅读：Python 教程

准备工作

在开始编写程序之前，我们需要先准备一个二叉树供我们测试使用。为了简便起见，我们使用Python中的字典数据类型来表示二叉树。字典的一个键表示节点的值，而该键所对应的值则是一个元组，包含左子树和右子树指向的节点值。

接下来，我们将使用以下的字典作为我们的二叉树例子：

tree = {3: (1, 4),
        1: (None, 2),
        4: (None, 8),
        2: (7, None),
        8: (None, 5),
        7: (None, None),
        5: (None, None)}

在这个例子中，节点3是二叉树的根节点。节点1和节点4分别是节点3的左子树和右子树。以此类推，我们可以通过查找任意节点来查看它的父节点和所有祖先节点。

查找最近公共祖先

为了查找二叉树的最近公共祖先，我们需要定义一个函数来帮助我们递归查找每个节点的祖先。

def find_ancestors(root, value, path):
    """find all ancestors of a given node"""
    if not root:
        return False
    path.append(root)
    if root == value:
        return True
    if (root.left and find_ancestors(root.left, value, path)) or \
            (root.right and find_ancestors(root.right, value, path)):
        return True
    path.pop()
    return False

这个函数接受三个参数：

root，表示二叉树的根节点；
value，表示需要查找祖先节点的节点的值；
path，表示从根节点到当前被查找的节点所经过的路径。

我们首先将当前的节点添加到path中。接着，我们递归查找该节点是否为目标节点以及该节点的子节点是否包含目标节点。如果目标节点或者目标节点的子节点被找到，则查找结束。否则，我们需要将当前节点弹出path。函数最终返回一个布尔值来表示是否找到目标节点。

在得到每个节点的祖先节点后，我们需要编写一个函数来查找两个节点的最近公共祖先。

def lowest_common_ancestor(root, node1, node2):
    """find lowest common ancestor of two nodes"""
    path1 = []
    path2 = []
    find_ancestors(root, node1, path1)
    find_ancestors(root, node2, path2)
    lca = None
    for p1, p2 in zip(path1, path2):
        if p1 == p2:
            lca = p1
        else:
            break
    return lca

这个函数接受三个参数：

root，表示二叉树的根节点；
node1，表示第一个需要查找最近公共祖先的节点；
node2，表示第二个需要查找最近公共祖先的节点。

函数首先调用find_ancestors()函数来分别查找两个节点的祖先。然后，我们创建两个空列表，path1和path2，用于储存两个节点的祖先路径。接着，在循环中，我们逐一比较path1和path2中的元素，记录最后一个相同的元素作为最近公共祖先节点。最后，我们返回最近公共祖先节点的值。

下面是一个完整的程序，包含了树的定义、查找祖先和查找最近公共祖先的函数。程序运行后将输出最近公共祖先的值，即为2。

tree = {3: (1, 4),
        1: (None, 2),
        4: (None, 8),
        2: (7, None),
        8: (None, 5),
        7: (None, None),
        5: (None, None)}

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

def find_ancestors(root, value, path):
    """find all ancestors of a given node"""
    if not root:
        return False
    path.append(root)
    if root.val == value:
        return True
    if (root.left and find_ancestors(root.left, value, path)) or \
            (root.right and find_ancestors(root.right, value, path)):
        return True
    path.pop()
    return False

def lowest_common_ancestor(root, node1, node2):
    """find lowest common ancestor of two nodes"""
    path1 = []
    path2 = []
    find_ancestors(root, node1, path1)
    find_ancestors(root, node2, path2)
    lca = None
    for p1, p2 in zip(path1, path2):
        if p1.val == p2.val:
            lca = p1
        else:
            break
    return lca.val

# create binary tree from dictionary
root = Node(3)
nodes = {3: root}
for key, val in tree.items():
    if key not in nodes:
        nodes[key] = Node(key)
    if val[0] is not None:
        nodes[key].left = nodes[val[0]]
    if val[1] is not None:
        nodes[key].right = nodes[val[1]]

# find lowest common ancestor of nodes with values 2 and 8
lca_value = lowest_common_ancestor(root, 2, 8)
print(lca_value)  # output: 2