日野弥生：勉強しよう
LeetCode 235 - 二叉搜索树的最近公共祖先
发表于2025年03月23日
二叉搜索树，它首先是二叉树，所以针对二叉树的共同祖先的解决方案，给二叉搜索树也适用。
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if not root or root == q or root == p:
return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if left and right:
return root
elif left and not right:
return left
else:
return right但是因为二叉搜索树具有有序性，所以可以通过迭代法遍历树降低栈深度。
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
ancestor = root
while True:
if p.val < ancestor.val and q.val < ancestor.val:
ancestor = ancestor.left
elif p.val > ancestor.val and q.val > ancestor.val:
ancestor = ancestor.right
else:
break
return ancestor