LCA最近公共祖先算法

在树（如二叉树）中，LCA（Lowest Common Ancestor）指的是两个节点的最近公共祖先节点。以下是一个二叉树中寻找LCA的Java代码示例：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

public class LowestCommonAncestor {

    public static TreeNode findLCA(TreeNode root, TreeNode node1, TreeNode node2) {
        if (root == null || root == node1 || root == node2) {
            return root;
        }

        TreeNode leftLCA = findLCA(root.left, node1, node2);
        TreeNode rightLCA = findLCA(root.right, node1, node2);

        if (leftLCA != null && rightLCA != null) {
            return root;  // root is the LCA
        }

        return (leftLCA != null) ? leftLCA : rightLCA;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(5);
        root.right = new TreeNode(1);
        root.left.left = new TreeNode(6);
        root.left.right = new TreeNode(2);
        root.right.left = new TreeNode(0);
        root.right.right = new TreeNode(8);
        root.left.right.left = new TreeNode(7);
        root.left.right.right = new TreeNode(4);

        TreeNode node1 = root.left;
        TreeNode node2 = root.right;
        TreeNode lca = findLCA(root, node1, node2);

        System.out.println("Lowest Common Ancestor of " + node1.val + " and " + node2.val + " is: " + lca.val);
    }
}

在这个示例中，findLCA 方法使用递归的方式在二叉树中寻找两个给定节点的最近公共祖先。它首先检查根节点是否为其中之一，然后递归搜索左子树和右子树，最终找到最近公共祖先。

请注意，这个示例是基于二叉树的LCA算法，实际应用中可能需要根据具体的数据结构和问题进行适当的修改。