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

Question

我有一个如下的二叉树。我需要找到最不常见的祖先（LCA）。例如6和4的LCA为1，4和5的LCA为2。

    1
   / \
  2   3
 / \ / \
4  5 6  7

谁能建议我该如何解决这个问题？

Answer 1

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

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;
    }
}