Python算法——最近公共祖先

Python中的最近公共祖先（Lowest Common Ancestor，LCA）算法详解

最近公共祖先（Lowest Common Ancestor，LCA）是二叉树中两个节点的最低共同祖先节点。在本文中，我们将深入讨论最近公共祖先问题以及如何通过递归算法来解决。我们将提供Python代码实现，并详细说明算法的原理和步骤。

最近公共祖先问题

给定一个二叉树和两个节点p、q，找到这两个节点的最近公共祖先。

递归算法求解最近公共祖先

递归算法是求解最近公共祖先问题的一种常见方法。从根节点开始，递归地遍历左右子树，查找包含节点p和节点q的最小子树。递归的终止条件是遇到null节点或找到节点p或节点q。

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

class Solution:
    def lowest_common_ancestor(self, root, p, q):
        if not root or root == p or root == q:
            return root

        left_lca = self.lowest_common_ancestor(root.left, p, q)
        right_lca = self.lowest_common_ancestor(root.right, p, q)

        if left_lca and right_lca:
            return root
        return left_lca or right_lca
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

示例

考虑以下二叉树：

3
1

/
5 1
/ \ /
6 2 0 8
/
7 4

# 构建二叉树
root = TreeNode(3)
root.left = TreeNode(5)
root.right = TreeNode(1)
root.left.left = TreeNode(6)
root.left.right = TreeNode(2)
root.right.left = TreeNode(0)
root.right.right = TreeNode(8)
root.left.right.left = TreeNode(7)
root.left.right.right = TreeNode(4)

sol = Solution()
p = root.left
q = root.right
lca = sol.lowest_common_ancestor(root, p, q)
print("节点 {} 和节点 {} 的最近公共祖先是节点 {}".format(p.val, q.val, lca.val))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

输出结果：

节点 5 和节点 1 的最近公共祖先是节点 3
1

这表示在给定的二叉树中，节点5和节点1的最近公共祖先是节点3。递归算法在解决最近公共祖先问题时具有简洁而高效的特性。通过理解算法的原理和实现，您将能够更好地处理树结构问题。