Leecode 面试题 #68 - II. 二叉树的最近公共祖先

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:

        return self.search(root, p, q)
    def search(self, node, p, q):
        if not node or node.val == p.val or node.val == q.val:
            return node

        r = self.search(node.right, p, q)
        l = self.search(node.left, p, q)

        if r and l:
            return node

        return r if r else l