在二叉树中寻找最不常见的祖先 [英] Finding Least Common Ancestor in Binary Tree

问题描述

可能的重复:
我如何找到二叉树中两个节点的共同祖先?
二叉树的第一个共同祖先

我有一个二叉树，如下所示.我需要找到最不常见的祖先(LCA).例如6和4的LCA是1，4和5的LCA是2.

I have a binary tree as below. I need to find the least common ancestor (LCA). e.g LCA of 6 and 4 is 1, LCA of 4 and 5 is 2.

    1
   / 
  2   3
 /  / 
4  5 6  7 

谁能建议我应该如何处理和解决这个问题?

Can anyone please suggest how should I approach and solve this problem?

推荐答案

从一个普通的深度优先搜索算法开始:

Start with an ordinary depth-first search algorithm:

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.

Now, adapt this to take two "target" parameters, target1 and target2.

当搜索 target1 向左移动，搜索 target2 向右移动时，您就找到了 LCA.

When the search for target1 takes you left, and the search for target2 takes you right, you've found the LCA.

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

This assumes that both targets actually do exist. If you need to assert that they do, you'll need to continue the search after finding the potential 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;
    }
}

这篇关于在二叉树中寻找最不常见的祖先的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！