Python中的最近公共祖先（Lowest Common Ancestor，LCA）算法详解
最近公共祖先（Lowest Common Ancestor，LCA）是二叉树中两个节点的最低共同祖先节点。在本文中，我们将深入讨论最近公共祖先问题以及如何通过递归算法来解决。我们将提供Python代码实现，并详细说明算法的原理和步骤。
最近公共祖先问题
给定一个二叉树和两个节点p、q，找到这两个节点的最近公共祖先。
递归算法求解最近公共祖先
递归算法是求解最近公共祖先问题的一种常见方法。从根节点开始，递归地遍历左右子树，查找包含节点p和节点q的最小子树。递归的终止条件是遇到null节点或找到节点p或节点q。
代码语言：javascript复制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示例
考虑以下二叉树：
代码语言：javascript复制3/ 5 1 / / 6 2 0 8 / 7 4
代码语言：javascript复制# 构建二叉树
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))输出结果：
代码语言：javascript复制节点 5 和节点 1 的最近公共祖先是节点 3这表示在给定的二叉树中，节点5和节点1的最近公共祖先是节点3。递归算法在解决最近公共祖先问题时具有简洁而高效的特性。通过理解算法的原理和实现，您将能够更好地处理树结构问题。
