LC 236二叉树的最近公共祖先Lowest Common Ancestor of a Binary Tree　中等

求二叉树中两个指定节点的最近公共祖先。

思路 递归分治：命中 p/q 返回自身；左右各中其一则当前为 LCA，否则取非空一侧。时间 O(n)。

class Solution:
    def lowestCommonAncestor(self, root, p, q):
        if not root 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
        return left or right