二叉树的最近公共祖先

问题拆解

在一棵普通二叉树里找 p、q 的最近公共祖先（LCA）。注意题目允许节点是自己的祖先，所以当 p 本身是 q 的祖先时，答案就是 p。

朴素做法是先各自找出根到 p、根到 q 的路径，再比对两条路径最后一个相同的节点。能做，但要额外存路径，而且“找路径”本身就得递归一遍。其实可以把判断融进一次后序遍历：站在任意节点上问左右子树“你们那边有没有 p 或 q”，如果两边都说有，p、q 必然分居两侧，当前节点就是它们最深的汇合点。

让递归函数的返回值携带明确语义：在这棵子树里找到了 p 或 q 就返回那个节点，否则返回空。LCA 是自底向上第一个“左右都非空”的节点。

后序递归：左右各找一遍

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) {
        return root; // 碰到 p 或 q 就不必再往下，直接上报
    }
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    if (left != null && right != null) {
        return root; // p、q 分居两侧，当前节点就是 LCA
    }
    return left != null ? left : right; // 只命中一边，把结果继续上传
}

def lowestCommonAncestor(root, p, q):
    if root is None or root is p or root is q:
        return root  # 碰到 p 或 q 就不必再往下，直接上报
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)
    if left and right:
        return root  # p、q 分居两侧，当前节点就是 LCA
    return left or right  # 只命中一边，把结果继续上传

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if root == nil || root == p || root == q {
        return root // 碰到 p 或 q 就不必再往下，直接上报
    }
    left := lowestCommonAncestor(root.Left, p, q)
    right := lowestCommonAncestor(root.Right, p, q)
    if left != nil && right != nil {
        return root // p、q 分居两侧，当前节点就是 LCA
    }
    if left != nil {
        return left
    }
    return right
}

use std::rc::Rc;
use std::cell::RefCell;

// 题目保证节点值互不相同，Rust 版用值比较代替指针比较
pub fn lowest_common_ancestor(
    root: Option<Rc<RefCell<TreeNode>>>,
    p: Option<Rc<RefCell<TreeNode>>>,
    q: Option<Rc<RefCell<TreeNode>>>,
) -> Option<Rc<RefCell<TreeNode>>> {
    let node = root?;
    let pv = p.as_ref().unwrap().borrow().val;
    let qv = q.as_ref().unwrap().borrow().val;
    let v = node.borrow().val;
    if v == pv || v == qv {
        return Some(node); // 碰到 p 或 q 就直接上报
    }
    let left = Self::lowest_common_ancestor(node.borrow().left.clone(), p.clone(), q.clone());
    let right = Self::lowest_common_ancestor(node.borrow().right.clone(), p, q);
    match (left, right) {
        (Some(_), Some(_)) => Some(node), // 分居两侧，当前节点就是 LCA
        (l, r) => l.or(r),
    }
}

返回值的语义要咬死：它不是“这棵子树的 LCA”，而是“这棵子树里找到的 p 或 q（或已确定的 LCA）”。三种情况各自成立——左右都非空，说明两个目标第一次在这里汇合，返回当前节点；只有一边非空，说明两个目标都在那一边（或只找到了一个），原样上传；都为空，返回空。

最容易被忽略的是第一行的短路：一旦 root 就是 p 或 q，立刻返回，不再往下搜。这正确处理了“p 是 q 的祖先”的情形——另一个目标一定在它的子树里，不搜也知道答案是它。而汇合点一旦确定，left、right 中只有一个非空，这个答案会被一路原样传回根，不会被中途覆盖。

复杂度

指标	复杂度	原因
时间	`O(n)`	每个节点最多访问一次
空间	`O(h)`	递归栈深度为树高，最坏退化成 O(n)

可以迁移的模式

给递归返回值定一个单一、明确的语义，父节点只负责组合子结果；
“两边都命中才在此汇合”的判断，天然要求后序（先左右后自身）；
目标节点本身可以作为递归终止条件，顺带覆盖“一个是另一个祖先”的边界。

树上求“汇合点”类的问题，几乎都是这套后序 + 返回值语义的变体。