最近公共祖先

主要考验递归的掌握

例题

# 分类讨论 
# 1.如果当前节点是p或q，则其为公共祖先，直接返回。当前节点为空为空返回None。
# 2.递归左右子树，如果p,q分别存在左右子树中，返回当前节点。
# 3.如果p,q 仅存在于左子树，向左递归。仅存在于右子树，向右递归。
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if root is None or root is p or root is q:
            return root
        left=self.lowestCommonAncestor(root.left,p,q)
        right=self.lowestCommonAncestor(root.right,p,q)
        if left and right:
            return root
        if left:
            return left
        return right

# 可以用上面的普通解法，但是最好用上二叉搜索树的性质，主要判断当前节点的值与p和q的关系。
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if p.val>q.val:
            temp=p
            p=q
            q=temp
        if root is p or root is q:
            return root
        if p.val<root.val<q.val:
            return root
        return self.lowestCommonAncestor(root.left,p,q) if root.val>q.val else self.lowestCommonAncestor(root.right,p,q)