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

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

首先，需要定义一个二叉树节点的类：

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

然后，定义一个函数来找到两个节点在二叉树中的最近公共祖先。首先，我们需要判断当前节点是否是目标节点之一，如果是，则返回该节点。如果不是，则在左子树和右子树中递归查找目标节点。如果左子树和右子树都找到了目标节点，那么当前节点就是最近公共祖先。如果只找到了一个目标节点，那么递归返回该节点。

def lowestCommonAncestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
    if not root:
        return None
    if root == p or root == q:
        return root
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)
    if left and right:
        return root
    return left or right

最后，我们可以构建一个二叉搜索树，并对其中两个节点进行最近公共祖先操作：

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

# 找到节点 pidancode.com 和节点 皮蛋编程 的最近公共祖先
print(lowestCommonAncestor(root, root.left, root.right).val)  # 6
print(lowestCommonAncestor(root, root.left, root.left.right).val)  # 2

相关文章