我认为可以根据父母名单坚持使用您的孩子地图。您只需要一个递归函数来查找父母是否已经是祖先。看下面的代码。
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class AncestorTracker {
private final Map<String, List<String>> childToParentMappings = new HashMap<String, List<String>>();
public void addChildParentMapping(String child, String parent) {
List<String> existingParents = childToParentMappings.get(child);
if (existingParents == null) {
existingParents = new ArrayList<String>();
childToParentMappings.put(child, existingParents);
}
if (!existingParents.contains(parent)) {
existingParents.add(parent);
}
}
public boolean isAncestor(String child, String ancestor) {
boolean result = false;
if (childToParentMappings.containsKey(child)) {
List<String> immedidateParents = childToParentMappings.get(child);
if (immedidateParents.contains(ancestor)) {
result = true;
} else {
for (String immediateParent : immedidateParents) {
if (isAncestor(child, immediateParent)) {
result = true;
break;
}
}
}
}
return result;
}
public static void main(String[] args) {
AncestorTracker ancestorTracker = new AncestorTracker();
String[][] pairs = { {"x", "y"}, {"a", "b"}, {"b", "x"}, {"a", "y"} };
for (String[] aPair : pairs) {
String child = aPair[1];
String parent = aPair[0];
if (ancestorTracker.isAncestor(child, parent)) {
System.out.println(child + " is already a decendent of " + parent);
} else {
ancestorTracker.addChildParentMapping(child, parent);
}
}
}
}