如何求二叉树中两个节点的最近公共祖先？

直接回答：递归后序遍历：在子树中查找 p 和 q，若当前节点为空或就是 p/q 则直接返回当前节点；否则看左右子树的返回——两边都非空说明 p、q 分居两侧，当前节点就是 LCA；只有一边非空则返回非空那侧的结果。时间 O(n)、空间 O(h)（递归栈）。

展开解析：这个写法的精髓在于返回值承载了「该子树中找到几个目标」的信息：左右都找到意味着分叉点即答案，而答案一旦产生就会一路向上原样传递。前提是两个节点都存在于树中；若不保证存在，需要在返回结构上带找到数量的标记，不能只看非空。特例优化是二叉搜索树：利用有序性从根开始，p、q 都小于当前节点往左、都大往右、否则当前节点即 LCA，时间 O(h)。工程变体常考：节点带 parent 指针时退化成「链表求交点」（各自向上走等长路径）；离线批量查询可用 Tarjan 并查集做到近 O(n + q)。追问方向：LCA 与树上路径问题（距离 = depth[p]+depth[q]−2·depth[lca]）的关系。

示例：

def lowest_common_ancestor(root, p, q):
    if root is None or root is p or root is q:
        return root
    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)
    if left and right:
        return root
    return left or right