使用Python找出给定节点二叉树最低公共祖先的程序

在二叉树中，最低公共祖先是指两个节点在树上的最近公共祖先节点。如下图所示，节点4和节点5的最低公共祖先是节点2。

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

问题解决方法

本文将提供2种方法来解决此问题：递归和存储父节点。

递归

在二叉树中查找两个节点的最低公共祖先，最直接的方法是递归遍历整棵树。

首先，在根节点中查找给定节点p和q，如果当前节点为None或者等于p或q，则返回当前节点。
接着，递归查找左右子树，如果左右子树中均存在p或q，则当前节点就是最低公共祖先。
如果只有一个子树存在p或q，则递归返回该子树。如下是递归实现的代码示例。

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

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if root is None or root == p or root == q:
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if left is None:
            return right
        if right is None:
            return left
        return root

递归方法时间复杂度为O(n)，其中n是节点的数量。这种方法的空间复杂度最差为O(n)，因为递归可能使用系统栈空间。

存储父节点

另一种方法是使用哈希表存储每个节点的父节点，然后在p和q之间进行迭代，直到它们到达公共祖先为止。

首先，从给定节点p和q开始遍历，并将它们的每个祖先（父节点、祖父节点等）添加到集合中。
然后，从节点q开始迭代，一直遍历到根节点，并将所有访问过的节点添加到另一个集合中。
最后，从节点p开始迭代，一直遍历到根节点，直到遇到第一个在集合中出现的节点。
该节点即为最低公共祖先。如下是该方法的代码实现示例。

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        parent = {root: None}
        # 存储每个节点的父节点
        while p not in parent or q not in parent:
            if root.left:
                parent[root.left] = root
                root = root.left
            if root.right:
                parent[root.right] = root
                root = root.right
        # 记录p节点到根节点的路径
        ancestors = set()
        while p:
            ancestors.add(p)
            p = parent[p]
        # 找到第一个q节点的祖先在p路径中出现的节点
        while q not in ancestors:
            q = parent[q]
        return q

这种方法的时间复杂度为O(n)，空间复杂度为O(n)。

测试

我们定义一个树类来构造二叉树，然后测试这两种算法的效率和正确性。

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

def build_tree(nodes, i):
    if i>=len(nodes):
        return None
    if not nodes[i]:
        return None
    root = Tree(nodes[i])
    root.left = build_tree(nodes, 2*i+1)
    root.right = build_tree(nodes, 2*i+2)
    return root

# 测试
nodes = [1, 2, 3, 4, 5]
root = build_tree(nodes, 0)

s = Solution()
# 测试递归方法
assert s.lowestCommonAncestor(root, root.left.left, root.left.right).val == 2
assert s.lowestCommonAncestor(root, root.left.left, root.right).val == 1

# 测试存储父节点方法
assert s.lowestCommonAncestor(root, root.left.left, root.left.right).val == 2
assert s.lowestCommonAncestor(root, root.left.left, root.right).val == 1

通过测试，我们可以看出这两种方法在正确性上没有问题。