二叉树最近公共祖先：递归法与栈存路径法详解及代码实现

方法二：栈存路径法

public boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {
    if (root == null) {
        return false;
    }
    // 将当前节点压入路径
    stack.push(root);
    // 找到目标节点
    if (root == node) {
        return true;
    }
    // 递归搜索左子树
    boolean flg = getPath(root.left, node, stack);
    if (flg) {
        return true;
    }
    // 递归搜索右子树
    flg = getPath(root.right, node, stack);
    if (flg) {
        return true;
    }
    // 左右子树都没找到，弹出当前节点
    stack.pop();
    return false;
}

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null) {
        return null;
    }
    // 找到跟到 p 和 q 的路径
    Stack<TreeNode> stackp = new Stack<>();
    Stack<TreeNode> stackq = new Stack<>();
    getPath(root, p, stackp);
    getPath(root, q, stackq);
    // 对齐两个栈长度
    int sizep = stackp.size();
    int sizeq = stackq.size();
    int size = sizep - sizeq;
    if (size > 0) {
        // stacp 更长，弹出多余元素
        while (size != 0) {
            stackp.pop();
            size--;
        }
    } else {
        // stacq 更长，弹出多余元素
        size = sizeq - sizep;
        while (size != 0) {
            stackq.pop();
            size--;
        }
    }
    // 此时两个栈大小一样，
    // 同时弹出栈顶，找到相同的
    while (!stackp.isEmpty() && !stackq.isEmpty()) {
        if (stackp.peek().equals(stackq.peek())) {
            return stackp.peek();
        }
        stackp.pop();
        stackq.pop();
    }
    return null;
}

四、总结

通过递归法的'自底向上'回溯，以及栈存路径法的'路径对比'思路，我们可以高效求解二叉树的最近公共祖先问题——前者利用递归特性简化代码，后者通过显式路径存储更直观易懂。结合本文的思路分析与代码示例，你可以根据场景灵活选择解法，轻松应对这类二叉树算法题。