java - java中找到两个节点的最小公共(public)祖先

Question

我在 stackoverflow 上查看了很多其他答案，但找不到任何有效的东西，我要么得到根，要么返回 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

我们可以使用递归后序遍历来计算最低公共(public)祖先，这是我的 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 时，该节点将是最低公共(public)祖先。如果我错了或者您在理解代码时遇到困难，请告诉我