235. 二叉搜索樹的最近公共祖先
給定一個(gè)二叉搜索樹, 找到該樹中兩個(gè)指定節(jié)點(diǎn)的最近公共祖先喉祭。
百度百科中最近公共祖先的定義為：“對(duì)于有根樹 T 的兩個(gè)結(jié)點(diǎn) p煤禽、q港准，最近公共祖先表示為一個(gè)結(jié)點(diǎn) x鹃愤，滿足 x 是 p暴凑、q 的祖先且 x 的深度盡可能大（一個(gè)節(jié)點(diǎn)也可以是它自己的祖先）凛篙∈蜇遥”
例如，給定如下二叉搜索樹: 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
解釋: 節(jié)點(diǎn) 2 和節(jié)點(diǎn) 8 的最近公共祖先是 6呛梆。
解法1
class Solution:
def lowestCommonAncestor(self, root, p, q):
if root.val < p.val and root.val < q.val:
return self.lowestCommonAncestor(root.right, p, q)
elif root.val > p.val and root.val > q.val:
return self.lowestCommonAncestor(root.left, p, q)
else:
return root
