观察规律,可以发现,如果满足 p.Val <= 当前节点.Val <= q.Val,那么说明该节点就是 p 和 q 的最近公共祖先,返回当前节点的地址。如果不符合,就根据 p 和 q 的值判断去左子树找还是去右子树找。
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if p.val > q.val: #保证p小于等于q
p, q = q, p
if not root or p.val <= root.val and root.val <= q.val:
return root
elif q.val < root.val:
return self.lowestCommonAncestor(root.left, p, q)
else:
return self.lowestCommonAncestor(root.right, p, q)