题目

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

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

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

示例 2：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3：

输入：root = [1,2], p = 1, q = 2
输出：1

提示：

• 树中节点数目在范围 [2, 105] 内。
• -109 <= Node.val <= 109
• 所有 Node.val 互不相同 。
• p != q
• p 和 q 均存在于给定的二叉树中。

思路

规律：p、q节点要么在分叉点（最近公共祖先就是分叉交点），要么在同一边（最近公共祖先是两者中的一个）

利用后序遍历去找左右子树，如果找到p、q则返回，如果为空（没找到p、q）返回None

用left去记录遍历左子树的结果

用right去记录遍历右子树的结果

有4种情况：
（1）left、right == null，说明都没有找到，p、q节点不在当前访问的节点的左右子树上，return None

（2）left为空，right不为空，说明p、q在右子树中，那么right就是最近公共祖先，return right（left不为空，right为空同理）

（3）left、right都不为空：说明p、q在当前访问的节点的左右子树上，当前节点就是最近公共祖先，return node

代码

# 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.f(root, p ,q)

    # 递归函数：利用后序遍历在左右子树中找p、q
    def f(self, node: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if node == None or node == p or node == q:   # 如果当前节点是p、q直接返回
            return node
        left = self.f(node.left, p, q)   # 往左子树找
        right = self.f(node.right, p, q) # 往右子树找
        if left == None and right == None: return None   # 如果都为空，说明不在当前节点下
        if left and right: return node   # 如果都不为空，说明分别位于当前节点的左右子树，那么当前节点就是LCA
        return left if left else right   # 如果其中一个为空，一个不为空，说明p、q在同一边，那么不为空的left/right就是LCA