236.二叉树的最近公共祖先

https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/

一：递归

对函数lowestCommonAncestor(root, p, q)

情况1：p、q都在以root为根的树中，函数返回p、q的最近公共祖先

情况2：p、q都不在以root为根的树中，返回null

情况3：p、q只有一个在以root为根的树中，为了向上搜寻，函数应返回root（加上p在，q不在，找root和q的公共祖先必然也是p和q的公共）

问题：对情况1，如何确定root一定是最近的公共祖先？由于是后序遍历，从下往上，第一次相交在root，因此一定是最近

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if root  == None:
            return None
        # 根据情况3，root是p或q其中一个（p和q必然是不同节点）时，应返回root
        if root == p or root == q:
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        #情况1
        #左子和右子树的公共祖先都非空， 很明显root就是左右子树的公共祖先
        if left != None and right != None:
            return root
        #情况2
        if left == None and right == None:
            return None
        #情况3
        #剩下的情况为：有且只有一个为空
        return left if left != None else right