在一棵树T中两个结点u和v的最近公共祖先(LCA),是树中以u和v为其后代的深度最大的那个结点。现给定某二叉搜索树(BST)中任意两个结点,要求你找出它们的最近公共祖先。
时间: 2023-06-14 08:07:19 浏览: 69
对于二叉搜索树,可以利用其性质进行查找最近公共祖先。
从根节点开始,如果当前节点的值比两个节点的值都大,则最近公共祖先在当前节点的左子树中;如果当前节点的值比两个节点的值都小,则最近公共祖先在当前节点的右子树中;否则当前节点即为最近公共祖先。
具体实现可以用递归或者迭代的方式进行,下面是一个递归的示例代码:
```python
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 not root:
return None
if root.val > p.val and root.val > q.val:
return self.lowestCommonAncestor(root.left, p, q)
elif root.val < p.val and root.val < q.val:
return self.lowestCommonAncestor(root.right, p, q)
else:
return root
```
其中,root表示当前节点,p和q表示要查找最近公共祖先的两个节点。如果当前节点的值比两个节点的值都大,则递归查找左子树;如果当前节点的值比两个节点的值都小,则递归查找右子树;否则返回当前节点即为最近公共祖先。