Найти наименее общего предка двух узлов в Java

Question

Я посмотрел на множество других ответов на stackru и не могу найти ничего, что работает, я либо получаю root, либо сам вернул node1, я не уверен, как сделать это рекурсивно, и перепробовал много раз, заканчивая так же. Любая помощь будет принята с благодарностью!

Вот мой код:

private static Node findLCA(Node node1, Node node2) {
    Node temp1 = node1, temp2 = node2, currentLargest = null;
    int largestDepth = 0;
    boolean found = false;
    if(node1 == null || node2 == null){
        return null;
    } else{
        while(found == false){
            if(temp1.getParent() != null && temp2.getParent() != null && temp1.getParent() == temp2.getParent() && nodeDepth(temp1.getParent()) > largestDepth){
                largestDepth = nodeDepth(temp1.getParent());
                currentLargest = temp1;
                temp1 = temp1.getParent();
                temp2 = temp2.getParent();
            } else if(temp1.getParent() != null){
                temp1 = temp1.getParent();
            } else if(temp2.getParent() != null){
                temp2 = temp2.getParent();
            }
            if(temp1.getParent() == null && temp2.getParent() == null){
                found = true;
            }

        }
        if(nodeDepth(temp1) >= largestDepth){
            return temp1;
        } else{
            return currentLargest;
        }
    }
}

Я отредактировал его, чтобы составить список предков каждого узла, но я не уверен, как проверять каждый из них, чтобы увидеть, совпадают ли элементы в списке, так как они обычно имеют разные размеры.

Вот новый код:

ArrayList<PhyloTreeNode> list1 = new ArrayList<PhyloTreeNode>();
    ArrayList<PhyloTreeNode> list2 = new ArrayList<PhyloTreeNode>();

    if(node1 == null || node2 == null){
        return null;
    } else{
        if(node1.getParent() != null){
            list1.add(node1.getParent());
            findLeastCommonAncestor(node1.getParent(), node2);
        }
        if(node2.getParent() != null){
            list2.add(node2.getParent());
            findLeastCommonAncestor(node1, node2.getParent());
        }
    }

Answer 1

Мы можем использовать рекурсивный пост-порядок обхода для вычисления наименьшего общего предка. Вот моя реализация Java. Здесь a & b даны входные данные, для которых я должен найти наименьших общих предков.

public static int lowestcommanancestors(Node root,int a,int b){
 if(root==null)
  return 0;
 int x=lowestcommanancestors(root.left,a,b);
 int y=lowestcommanancestors(root.right,a,b);
 if(x+y==2){
  System.out.println(root.getData());
  return 0;
 }
 if(root.getData()==a || root.getData()==b){
  return x+y+1;
 }
 else{
  return x+y;
 }
 
}

Сначала я проверяю, присутствует ли данный входной узел в левом поддереве или нет, если да, просто верните 1, иначе 0, аналогично для правого поддерева. Когда сумма становится равной 2, в первый раз этот узел будет наименьшим общим предком. Скажите, если я ошибаюсь или у вас возникают трудности с пониманием кода