Модификация кода LCA для двоичного дерева, чтобы проверить, присутствует ли узел в Java

Question

У меня есть этот код, который рассчитывает 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;
            }

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

В противном случае выполните поиск слева и справа от дочерних элементов, чтобы увидеть, решает ли один из них проблему самостоятельно:

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

Теперь все случаи, в которых 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 в дереве.