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

Question

Я нашел это решение в 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;
}

Answer 1

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

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

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

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

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

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

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

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

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

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

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