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

前置

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

递归1

class Solution:
    def __init__(self):
        self.ret = None

    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # 后序遍历
        def order(root):
            if not root: return root
            left = order(root.left)
            right = order(root.right)
            
            if p in (left, root, right) and q in (left, root, right):
                self.ret = root
                return None
            elif p in (left, root, right):
                return p
            elif q in (left, root, right):
                return q
            else:
                return None

        order(root)
        return self.ret

递归2

def lowestCommonAncestor(root, p, q):
    if not root: return root
    if root == p or root == q: return root
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)
    if left and right: return root
    return left if left else right