java - 在二叉树中查找最小公祖

This question already has answers here:

How to find the lowest common ancestor of two nodes in any binary tree?
（34个答案）
First Common Ancestor of a Binary Tree
（1个答案）
可能重复：
How can I find the common ancestor of two nodes in a binary tree?
first common ancestor of a binary tree
我有一棵二叉树，如下所示。我需要找到最小共同祖先（LCA）。例如，6和4的LCA为1，4和5的LCA为2。

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

有人能建议我该如何解决这个问题吗？

最佳答案

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

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

关于java - 在二叉树中查找最小公祖，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/12056068/