题解 | #二叉搜索树的最近公共祖先#

二叉搜索树的最近公共祖先

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)
全部评论

相关推荐

qq乃乃好喝到咩噗茶:院校后面加上211标签,放大加粗,招呼语也写上211
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务