题解 | #二叉搜索树的最近公共祖先#
二叉搜索树的最近公共祖先
https://www.nowcoder.com/practice/d9820119321945f588ed6a26f0a6991f
# 解题思路
因为是二叉搜索树,分情况讨论,然后递归。
1. 如果根节点等于p或q,返回根节点,如果p和q在根节点的两侧,返回根节点。
2. 否则,如果都小于根节点,递归左子节点,如果都大于根节点,递归右子节点。
# 草稿内容
# 解题思路
class Solution: def lowestCommonAncestor(self , root: TreeNode, p: int, q: int) -> int: # write code here if root.val == p or root.val == q: return root.val if min(p, q) < root.val < max(p, q): return root.val if root.val > max(p, q): return self.lowestCommonAncestor(root.left, p, q) if root.val < min(p, q): return self.lowestCommonAncestor(root.right, p, q)