在二叉树中寻找最小共同祖先

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