难度: Medium
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
示例 1:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 输出: 6 解释: 节点2和节点8的最近公共祖先是6。
示例 2:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 输出: 2 解释: 节点2和节点4的最近公共祖先是2, 因为根据定义最近公共祖先节点可以为节点本身。
说明:
运行时间: 76 ms
内存: 18.8 MB
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
while root:
if p.val > root.val and q.val > root.val:
root = root.right
elif p.val < root.val and q.val < root.val:
root = root.left
else:
return root
题解利用了二叉搜索树的性质：对于二叉搜索树的任意一个结点，其左子树的所有结点值都小于该结点值，其右子树的所有结点值都大于该结点值。因此，从根结点开始遍历，比较当前结点值与目标结点值 p 和 q 的大小关系，如果 p 和 q 的值都大于当前结点值，则最近公共祖先在当前结点的右子树中；如果 p 和 q 的值都小于当前结点值，则最近公共祖先在当前结点的左子树中；否则，当前结点就是 p 和 q 的最近公共祖先。
时间复杂度: 最坏 O(n)，平均 O(log(n))
空间复杂度: O(1)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
while root:
# 如果 p 和 q 的值都大于当前结点值，则在右子树中查找
if p.val > root.val and q.val > root.val:
root = root.right
# 如果 p 和 q 的值都小于当前结点值，则在左子树中查找
elif p.val < root.val and q.val < root.val:
root = root.left
# 否则，当前结点就是最近公共祖先
else:
return root
如果p和q中的一个是另一个的祖先，例如p是q的祖先，那么在算法执行过程中，当遍历到p时，会发现q位于p的子树中（左子树或右子树），而p位于其自身的位置上。由于此时p和q不可能同时大于或小于p的值，算法将直接返回p作为最近公共祖先。这是因为p是q的直接或间接父节点，同时也满足公共祖先的定义。
是的，该算法的实现假设所有节点值都是唯一的，这样才能通过值比较来确定节点的位置和寻找路径。如果二叉搜索树中存在重复值，仅使用值比较可能无法准确地确定节点的具体位置，因为相同的值可能出现在树的不同位置。如果存在重复值，算法需要调整为不仅比较节点值，而且还需要有机制来区分拥有相同值的不同节点，例如通过增加额外的标记或引用来区分同值的不同节点。
在二叉搜索树中，如果p和q位于当前节点root的两侧，即一个位于左子树，另一个位于右子树，这意味着从root出发到p和q的路径在root节点处分叉。根据最近公共祖先的定义，最近公共祖先是从根节点到两个目标节点的路径上的最后一个共同节点。在这种情况下，任何其他公共祖先必须位于root的祖先节点中，但这些祖先节点的路径不会同时延伸到p和q。因此，当前节点root是p和q的最低（最近）公共祖先。