给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大。” 例如,给定如下二叉搜索树(描述形式为叶子节点扩展后的先序序列):6,2,0,#,#,4,3,#,#,5,#,#,8,7,#,#,9,#,#, 【输入形式】 第一行为二叉搜索树 第二行为节点p 第三行为节点q 【输出形式】 该树中这两个指定节点的最近公共祖先 【样例输入】 6,2,0,#,#,4,3,#,#,5,#,#,8,7,#,#,9,#,#, 2 8 【样例输出】 6
时间: 2023-09-13 18:10:17 浏览: 35
以下是Python代码实现:
```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 p.val > q.val:
p, q = q, p
if root.val >= p.val and root.val <= q.val:
return root
elif root.val < p.val:
return self.lowestCommonAncestor(root.right, p, q)
else:
return self.lowestCommonAncestor(root.left, p, q)
```
其中,`TreeNode`为二叉树节点的定义,`lowestCommonAncestor`为求最近公共祖先的函数,其输入参数为二叉搜索树`root`和两个节点`p`、`q`,输出为最近公共祖先。具体实现中,首先判断`root`是否为空,若为空则直接返回`None`。然后比较`p`和`q`的值大小,若`p`的值大于`q`的值,则交换两者的值。接着,判断`root`的值是否在`p`和`q`的值之间,若是则说明`root`就是最近公共祖先,直接返回`root`。若`root`的值小于`p`的值,则说明`p`和`q`都在`root`的右子树中,因此需要继续在右子树中查找。若`root`的值大于`q`的值,则说明`p`和`q`都在`root`的左子树中,因此需要继续在左子树中查找。最终,可以得到最近公共祖先的节点。