236. 二叉树的最近公共祖先

难度：🟡 Medium | 标签：树、DFS | 状态：⬜ LeetCode 链接

思路

后序递归：

• 当前是 p 或 q → 返回当前
• 左右子树各自的递归结果都非空 → 当前是 LCA
• 一边非空一边空 → 返回非空那边

代码

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root || root == p || root == q) return root;
        auto* l = lowestCommonAncestor(root->left, p, q);
        auto* r = lowestCommonAncestor(root->right, p, q);
        if (l && r) return root;
        return l ? l : r;
    }
};

复杂度

• 时间 O(n)，空间 O(h)

易错 / 回顾

• p / q 一定在树里（题目保证），所以非空那边一定包含对应节点
• BST 版本（235）可以利用大小关系，O(h)
• 多次查询：用 Tarjan 离线或 LCA 倍增预处理