3

我有这个代码，它计算给定的Least common Ancestor两个nodes。Binary tree目前，它假设两个节点都存在。我可以编写一个辅助方法来检查节点是否存在，然后调用该LCABT方法。那将需要遍历树两次。我想知道是否有一种方法可以检查和处理当前代码中不存在节点的情况。

//LCA of Binary tree
            public static Node LCABT(Node root, int v1, int v2){
                if (root==null)
                    return null;
                if (root.data==v1 || root.data==v2){
                    return root;
                }
                Node left = LCABT(root.left,v1,v2);
                Node right = LCABT(root.right,v1,v2);

                if(left!=null && right!=null)
                    return root;
                else if (left!=null)
                     return left;
                else  if (right!=null)
                       return right;
                return null;
            }
4

1 回答 1

2

使函数返回一对(state, lca)。 state必须是以下之一：

0: Neither v1 nor v2 appear at or under root; lca is meaningless.
1: Only v1 appears at or under root; lca is meaningless.
2: Only v2 appears at or under root; lca is meaningless.
3: Both v1 and v2 appear at or under root, and have LCA equal to lca.

该功能应首先检查基本情况：

LCABT(Node root, int v1, int v2) {
    if (root == null) then return (0, null);

否则，递归它的左右孩子，看看他们中的一个是否能自己解决问题：

    (s1, lca1) = LCABT(root.left, v1, v2);
    (s2, lca2) = LCABT(root.right, v1, v2);

如果其中一个s1或s2为 3，则已找到 LCA（分别为lca1或lca2）并且可以立即返回。（事实上​​，你甚至可以通过s1 == 3在第二次调用之前检查是否获得加速LCABT()：如果是，那么我们已经有了 LCA，不需要第二次调用。）

    if (s1 == 3) then return (3, lca1);
    if (s2 == 3) then return (3, lca2);

否则，设置s = s1 | s2（即按位或）。如果s == 3那时我们知道那root是 LCA，但我们还没有考虑到它可以成为 LCA 的所有方式：它仍然可以是 LCA，当只有一个v1和v2出现在其子级上或下级时，只要另一个值本身root就是：

    s = s1 | s2;
    if (root.data == v1) then s = s | 1;
    if (root.data == v2) then s = s | 2;

现在所有rootLCA 的情况都隐含s == 3，所以如果s == 3那时我们可以(3, root)立即返回：

    if (s == 3) then return (3, root);

否则，最多有一个v1和v2是 at 或 under root，所以我们应该返回一个值来指示它是哪一个：

    return (s, null);
}

最后，最初的顶级调用LCABT()显然应该认为该函数只有在返回state值 3 时才成功。

与您的算法相比，该算法的另一个优点是它不会被树中的任何一个副本v1或v2树中的重复副本所愚弄。

于 2014-01-29T19:31:51.770 回答