Самый низкий общий предок - код объяснения

Question

LCA путем прохождения по порядку и порядку заказа был легко реализован и понят мной.

Но есть рекурсивный подход снизу вверх.

Я взглянул на код в Интернете и не понял ни одной строки:

Вот код:

public Node lowestCommonAncestor(int val1, int val2,Node root){
    if(root == null){
        return null;
    }
    if(root.data == val1 || root.data == val2){
        return root;
    }

    Node left = lowestCommonAncestor(val1, val2, root.left);
    Node right = lowestCommonAncestor(val1, val2, root.right);

    if(left != null && right != null){
        return root;
    }
    return left != null ? left : right;
}

val1 и val2 - это значения двух узлов, LCA которых необходимо найти.

Последняя строка, где я застрял.

return left != null ? left : right;

Кто-нибудь может это объяснить?

Спасибо.

Answer 1

// Method to find lowest common ancestor.
public Node lowestCommonAncestor(int val1, int val2,Node root){

    // Base condition to terminate.
    if(root == null){
        return null;
    }

    // While traversing, if we found root itself equal to val1/val2.
    // Then, root should be the lowest common ancestor.
    if(root.data == val1 || root.data == val2){
        return root;
    }

    // If not, do post-order traversing. Means, left node, then right 
    // node, then root iteslf (current node.)
    Node left = lowestCommonAncestor(val1, val2, root.left);
    Node right = lowestCommonAncestor(val1, val2, root.right);

    // While traversing, if we reach to a state, when root itself has left and 
    // right both children, then, this is the lowest common ancestor of val1, 
    // and val2. return this root.
    if(left != null && right != null){
        return root;
    }

    // If, root has only one child either  left or right child, then start 
    // traversing into that child.
    // If, root has no child, in that case. Return null. Means this tree does    
    // not contain lowest common ancestor of val1, and val2.
    return left != null ? left : right;
}

Я объяснил весь код, поместив комментарии. Я думаю, что это будет иметь больше смысла. Пожалуйста, пройдите. Если у вас все еще есть сомнения, не стесняйтесь спрашивать.

Answer 2

Это (своего рода) аккуратная реализация наивного подхода, но реализованная сверху вниз вместо стандартного снизу вверх. Давайте попробуем проанализировать, что делает lowestCommonAncestor(int val1, int val2,Node root) вернуть.

left будет не нулевым, если хотя бы один из val1 а также val2 находится в левом поддереве root, Аналогично право будет не нулевым, если и только если хотя бы один из val1 а также val2 находится в правом поддереве root, Видимо, если заявление if(left != null && right != null){ будет верно, если и только если именно один из val1 а также val2 находится в левом поддереве и точно один из val1 а также val2 находится в правом поддереве. Таким образом, это произойдет только для самого низкого общего предка val1 а также val2(нарисуйте картинку, если вам нужно). Для этого узла будет возвращен корень. Для всех остальных узлов функция вернет lowestCommonAncestor в левом или правом поддереве, в зависимости от того, какое из них не является нулевым или нулевым, если оба являются нулевыми.

Таким образом, для всех узлов выше LCA, точно один из правого и левого будет не нулевым (как val1 а также val2 будет в одном из поддеревьев), и это будет корень поддерева, где находится LCA. Как следствие, возвращаемое значение вызова lowestCommonAncestor для всех узлов выше LCA будет сама LCA. Как следствие, вызов корня исходного дерева действительно будет LCA.