寻找最小共同祖先在二叉树 [英] Finding Least Common Ancestor in Binary Tree

问题描述

可能重复：
  <一href="http://stackoverflow.com/questions/1484473/how-can-i-find-the-common-ancestor-of-two-nodes-in-a-binary-tree">How我可以找到一个二叉树两个节点的共同祖先？
  的href="http://stackoverflow.com/questions/10133332/first-common-ancestor-of-a-binary-tree">共同祖先

Possible Duplicate:
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 LCA和5是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);
    }
}

现在，适应这需要两个目标参数，目标1和TARGET2。

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

当搜索目标1带你离开，并寻找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屋！