LeetCode难题236：二叉树的最近公共祖先

问题236：给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为：“对于有根树T的两个结点p、q，最近公共祖先表示为一个结点x，满足x是p、q的祖先且x的深度尽可能大（一个节点也可以是它自己的祖先）。”

这题思想分为以下三点：

• 如果p和q都不在一个节点的左子树，则继续搜索右子树；
• 如果p和q都不在一个节点的右子树，则继续搜索左子树；
• 如果一个节点的左、右子树分别包含p和q其中之一，则返回该节点。

完整代码：

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        def search(node):
            if not node:
                return None
            elif node.val == p.val or node.val == q.val:
                return node
            
            left_node = search(node.left)
            right_node = search(node.right)
            
            if not left_node:
                return right_node
            if not right_node:
                return left_node
            else:
                return node
        
        return search(root)

运行结果：