java - 修改二叉树的 LCA 代码以检查节点是否存在于 Java 中

Question

我有这段代码，它计算二叉树中给定的两个节点的Least common Ancestor。目前，它假设两个节点都存在。我可以编写一个辅助方法来检查节点是否存在，然后调用 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;
            }

Answer 1

让函数返回一对(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);

否则，递归它的左右 child ，看看是否有一个 child 自己解决了这个问题:

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

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

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

否则，设置s = s1 | s2(即按位或)。如果 s == 3 那么我们知道 root 是 LCA，但我们还没有考虑所有方式它可以是LCA:当 v1 和 v2 中只有一个出现在其子项中或下方时，它仍然可以是 LCA，前提是另一个值位于 root本身:

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

现在 root 是 LCA 的所有情况都意味着 s == 3，所以如果 s == 3 那么我们可以返回 (3, root) 立即:

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

否则，v1 和 v2 中最多有一个在 root 或之下，因此我们应该返回一个值来指示它是哪个:

    return (s, null);
}

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

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