地鼠的远亲题目的解决代码
时间: 2024-10-05 11:04:27 浏览: 19
地鼠的远亲题目通常涉及到图论中的“最近公共祖先”(Lowest Common Ancestor, LCA)问题,这是一个经典的计算机科学问题,常用于树形数据结构中寻找两个节点最近的共同祖先。这里我们假设有一个二叉搜索树(Binary Search Tree, BST),其中每个节点都有左孩子和右孩子,并且左孩子的值小于父节点,右孩子的值大于父节点。
这个问题的一个常见解法是使用递归。首先,如果根节点为空,返回null;如果其中一个节点的值小于另一个节点,那么它们的LCA一定在根节点的右侧,反之则在左侧。然后对这个子树递归求解。
以下是Python代码示例:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def lowestCommonAncestor(root, p, q):
if not root:
return None
# 如果p 或 q 小于 root,那么LCA 在左半边
if p.val < root.val and q.val < root.val:
return lowestCommonAncestor(root.left, p, q)
elif p.val > root.val and q.val > root.val:
# 同理,LCA 在右半边
return lowestCommonAncestor(root.right, p, q)
# 找到了一个节点的值在这两个之间,这就是我们的LCA
return root
```
阅读全文