题解 | #在二叉树中找到两个节点的最近公共祖先#

class Solution:
    def lowestCommonAncestor(self , root: TreeNode, o1: int, o2: int) -> int:
        # write code here
        # base case，root为空，返回-1
        if root is None:
            return -1
        
        # 找到o1或者o2就返回其值，来表示找到
        if o1 == root.val or o2 == root.val:
            return root.val
        
        # 如果root不是o1或者o2，表示还没找到，继续递归，到左右子树去找
        # 找到一定会返回o1或者o2的值，即不为-1
        # 找不到的话会因为叶结点的子孩子两个都为-1，导致一路-1返回过去，直到找到o1或者o2
        
        left = self.lowestCommonAncestor(root.left, o1 ,o2)
        right = self.lowestCommonAncestor(root.right, o1, o2)
        
        # 此时只要不含有o1和o2就会一路返回-1
        # 若o1和o2在同一子树上，即有一侧会返回-1，此时则返回该子节点的val，它就是最近公共祖先
        # 不然就不在同一侧子树上，即最近公共祖先就为root本身，返回root.val
        if left == -1:
            return right
        if right == -1:
            return left
        
        return root.val