问题背景

在二叉树结构中定位两个指定节点的最近公共祖先（LCA）是经典的树形算法问题。该问题要求找到距离两个目标节点最近、且同时为它们祖先的节点。以下介绍两种不同维度的解题策略：基于父节点映射的迭代回溯法，以及基于后序遍历的状态压缩递归法。

方案一：父节点映射与路径回溯

核心思想是将树形结构转化为隐式的向上链表。首先通过深度优先搜索遍历整棵树，使用哈希表记录每个子节点对应的父节点引用。建立完整映射关系后，从第一个目标节点开始沿父指针向上回溯，并将经过的节点值存入哈希集合中。随后从第二个目标节点执行相同的向上遍历操作，首次与集合发生碰撞的节点即为所求的最近公共祖先。

class Solution {
    private final Map parentMap = new HashMap<>();
    private final Set<Integer> visitedPath = new HashSet<>();

    private void traverseAndRecord(TreeNode node) {
        if (node == null) return;
        if (node.left != null) {
            parentMap.put(node.left.val, node);
            traverseAndRecord(node.left);
        }
        if (node.right != null) {
            parentMap.put(node.right.val, node);
            traverseAndRecord(node.right);
        }
    }

    public TreeNode findLCA(TreeNode root, TreeNode nodeA, TreeNode nodeB) {
        traverseAndRecord(root);
        
        TreeNode curr = nodeA;
        while (curr != null) {
            visitedPath.add(curr.val);
            curr = parentMap.get(curr.val);
        }
        
        curr = nodeB;
        while (curr != null) {
            if (visitedPath.contains(curr.val)) {
                return curr;
            }
            curr = parentMap.get(curr.val);
        }
        return null;
    }
}

方案二：后序遍历与状态压缩递归

传统的递归解法通常依赖额外的布尔标志位来标记子树是否包含目标节点，导致代码结构冗余且需要维护类成员变量。实际上，可以利用后序遍历（左-右-根）的特性，让递归函数直接返回查找结果，从而实现逻辑的高度浓缩与无状态化。

递归的基准条件为：当前节点为空，或当前节点恰好等于目标节点之一，此时直接返回当前节点引用。在获取左右子树的递归返回值后，根据返回结果进行分支判断：

• 若左侧返回空引用，说明两个目标节点均位于右子树分支（或右子树已计算出公共祖先），直接透传右侧结果。
• 若右侧返回空引用，同理，直接透传左侧结果。
• 若左右两侧均返回非空节点，说明当前节点正是两条目标路径的首次交汇点，即最近公共祖先。

该设计天然兼容"一个目标节点本身就是另一个节点祖先"的边界场景。因为当递归首次命中某个目标节点时会立即向上返回，若另一节点位于其子树内，另一侧递归必为空，最终结果会正确向上传递该祖先节点，无需额外条件判断。

class Solution {
    public TreeNode findLCA(TreeNode current, TreeNode target1, TreeNode target2) {
        if (current == null || current == target1 || current == target2) {
            return current;
        }
        
        TreeNode leftRes = findLCA(current.left, target1, target2);
        TreeNode rightRes = findLCA(current.right, target1, target2);
        
        if (leftRes == null) {
            return rightRes;
        }
        if (rightRes == null) {
            return leftRes;
        }
        
        return current;
    }
}