Какой алгоритм использует этот код для поиска наименьшего общего предка бинарного дерева?

Я нашел это решение на Leetcode, пытаясь решить эту проблему:

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/

Кажется, все в Leetcode считают само собой разумеющимся, как это работает. Но я не понимаю. Что здесь происходит и какой алгоритм используется для нахождения LCA бинарного дерева?

public TreeNode lowestCommonAncestorBinaryTree(TreeNode root, TreeNode p, TreeNode q) {
    if(root==null) {
        return null;
    }
    if(root==p) {
        return p;
    }
    if(root==q) {
        return q;
    }
    TreeNode left = lowestCommonAncestorBinaryTree(root.left, p, q);
    TreeNode right = lowestCommonAncestorBinaryTree(root.right, p, q);
    if (left != null && right != null) {
        return root;
    }
    if(left!=null && right==null) {
        return left;
    }
    if(right!=null && left==null) {
        return right;
    }
    return null;
}

algorithm binary-tree lowest-common-ancestor
person Bob    schedule 25.01.2020    source источник
comment
Не существует такого понятия, как младший общий предок бинарного дерева; задача на самом деле просит вас найти наименьшего общего предка двух узлов в двоичном дереве.   -  person ruakh    schedule 26.01.2020

Ответы (1)


arrow_upward
1
arrow_downward

Довольно просто:

Код смотрит в корень дерева. Если корень равен p или q, он возвращает его.

Если его нет в корне, он ищет в левом и правом поддеревьях корня, повторяя процесс до тех пор, пока root на самом деле не станет p или q.

Затем идут 3 последних ifs.

  1. if (left != null && right != null) return root;

    Это означает, что он нашел один из узлов в левом поддереве корня, а другой — в правом поддереве корня, следовательно, корень — это LCA.

  2. if(left != null && right == null) return left;

    Это означает, что он нашел узел в левом поддереве, но не нашел узла в правом поддереве, тогда левый узел является родителем другого узла, следовательно, LCA.

  3. if(right != null && left == null) return right;

    Это означает, что он нашел узел в правом поддереве, но не нашел узла в левом поддереве, тогда правый узел является родителем другого узла, следовательно, LCA.

В противном случае узлов нет в дереве и нет LCA.

person Daniel    schedule 25.01.2020