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

本文介绍如何查找二叉树中两个节点的最近公共祖先（Lowest Common Ancestor, LCA）。LCA 问题在树形结构数据处理中非常常见，通常通过递归或迭代方法解决。

问题定义

给定一个二叉树和一个包含两个节点的集合，找到这两个节点的最近公共祖先。如果其中一个节点是另一个节点的子节点，则该节点为 LCA；如果树中不存在这两个节点，则返回 NULL。

递归解法

递归方法基于分治思想，将问题分解为查找左子树和右子树的 LCA，然后根据结果确定当前节点的角色。

操作步骤

1. 从根节点开始递归遍历树。
2. 如果当前节点为 NULL，返回 NULL。
3. 如果当前节点等于两个目标节点之一，返回当前节点。
4. 递归查找左子树和右子树的 LCA。
5. 如果左右子树的返回值都不为 NULL，则当前节点为 LCA。
6. 如果只有一侧返回值不为 NULL，则返回该侧的返回值。

代码示例

TreeNode* findLCA(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (root == NULL || root == p || root == q) {
        return root;
    }
    TreeNode* left = findLCA(root->left, p, q);
    TreeNode* right = findLCA(root->right, p, q);
    if (left != NULL && right != NULL) {
        return root;
    }
    return (left != NULL) ? left : right;
}

迭代解法

迭代方法通过栈或父指针记录节点访问路径，避免递归开销，适合大深度树。

操作步骤

1. 使用栈记录从根节点到当前节点的路径。
2. 分别从根节点出发，沿路径遍历到两个目标节点。
3. 比较两条路径，从底部开始回溯，第一个不同的节点即为 LCA。

代码示例

TreeNode* findLCAIterative(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (root == NULL) return NULL;
    stack path1, path2;
    bool foundP = false, foundQ = false;
    findPath(root, p, path1, foundP);
    findPath(root, q, path2, foundQ);
    if (!foundP || !foundQ) return NULL;
    TreeNode* lca = NULL;
    while (!path1.empty() && !path2.empty() && path1.top() == path2.top()) {
        lca = path1.top();
        path1.pop();
        path2.pop();
    }
    return lca;
}

void findPath(TreeNode* root, TreeNode* target, stack& path, bool& found) {
    if (root == NULL) return;
    path.push(root);
    if (root == target) {
        found = true;
        return;
    }
    findPath(root->left, target, path, found);
    if (found) return;
    findPath(root->right, target, path, found);
    if (!found) path.pop();
}

优化与注意事项

递归方法简洁但可能导致栈溢出，迭代方法更稳定但代码复杂度稍高。对于有父指针的二叉树，可使用双指针法从底部向上查找，效率更高。

实际应用中需考虑：

• 树是否为二叉搜索树（BST）？BST 中 LCA 可通过值比较直接查找。
• 节点是否重复？需确保唯一标识。
• 内存使用和性能瓶颈，特别是在大数据量时。