最近公共祖先

LeetCode题目地址

在root为根的二叉树中找A,B的LCA:

• 如果找到了就返回这个LCA
• 如果只碰到A，就返回A
• 如果只碰到B，就返回B
• 如果都没有，就返回null
  使用分治法的思想

def lowestCommonAncestor(self, root, A, B):
        # write your code here
        
        if root is None:
            return None
            
        if root is A or root is B:
            return root
        #分   
        left = self.lowestCommonAncestor(root.left, A, B)
        right = self.lowestCommonAncestor(root.right, A, B)
        #治
        if left is not None and right is not None:
            return root
        if left is not None:
            return left
        if right is not None:
            return right
        return None