在二叉树中找到最少的祖先

从普通的深度优先搜索算法开始：

public Node find(Node node, int target) {    if(node == null || node.value == target) {        return node;    }    if(node.value > target) {        return find(node.left, target);    } else {        return find(node.right, target);    }}

现在，将其修改为采用两个“目标”参数，即target1和target2。

当搜索target1带您离开，而搜索target2带您去时，您已经找到了LCA。

假设两个目标确实存在。如果需要断言它们确实如此，则需要在找到潜在的LCA之后继续搜索。

public Node findLca(Node node, int t1, int t2) {    if(node == null) {        return null;    }    if(node.value > t2 && node.value > t1) {        // both targets are left        return findLca(node.left, t1, t2);    } else if (node.value < t2 && node.value < t1) {        // both targets are right        return findLca(node.right, t1, t2);    } else {        // either we are diverging or both targets are equal        // in both cases so we've found the LCA        // check for actual existence of targets here, if you like        return node;    }}