二叉树最近公共祖先解法：递归法与栈存路径法

三、代码展示

方法一：递归法

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    // 当前节点为空，直接返回 null
    if (root == null) {
        return null;
    }
    // 当前节点是 p 或者 q，返回当前节点（祖先）
    if (root == p || root == q) {
        return root;
    }
    // 递归探索左子树，找到 p 和 q 的最近祖先
    TreeNode leftRet = lowestCommonAncestor(root.left, p, q);
    // 递归探索右子树，找到 p 和 q 的最近祖先
    TreeNode rightRet = lowestCommonAncestor(root.right, p, q);
    // 左子树和右子树都找到
    if (leftRet != null && rightRet != null) {
        return root;
    }
    // 左子树找到
    else if (leftRet != null) {
        return leftRet;
    } else {
        // 右子树找到
        return rightRet;
    }
}

方法二：栈存路径法

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) {
        // stackp 更长，弹出多余元素
        while (size != 0) {
            stackp.pop();
            size--;
        }
    } else {
        // stackq 更长，弹出多余元素
        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;
}

四、总结

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