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

Question

LCA by inorder и postorder traversal был легко реализован и понятен мной.

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

Я посмотрел на код в Интернете, и я не понял одну строку:

Вот код:

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

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

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