1600. 王位继承顺序
思路:前序遍历多分支树
1.用set集合来存放死亡的人数
2.用hashMap来存放每个父结点的子节点列表
3.每出生一个,把孩子存放到父结点的子节点列表中
4.在getInheritanceOrder()中,进行深度优先遍历,把没有去世的添加到答案中,然后遍历其所有子节点
代码:
private String king;
private Set<String> dead = new HashSet<>();//存死亡的人
private Map<String,List<String>>g = new HashMap<>();
//用哈希表来存储每个人的孩子
private List<String>ans = new ArrayList<>();//要返回的答案
//1600. 王位继承顺序---前序遍历多分支树
public void ThroneInheritance(String kingName) {
king = kingName;//继承王位
}
public void birth(String parentName, String childName) {
g.computeIfAbsent(parentName,k->new ArrayList<>()).add(childName);
//computeIfAbsent: 这是 Map 接口的一个方法,用于根据指定的键查找值。
// 如果键存在,则返回与键关联的值;
// 如果键不存在,则使用提供的函数计算值并将其与键关联,然后返回该值
//将 childName 添加到 parentName 的孩子列表中
}
public void death(String name) {
dead.add(name);
}
public List<String> getInheritanceOrder() {
ans.clear();
dfs(king);//进行深度优先遍历
return ans;
}
private void dfs(String x){
if (!dead.contains(x)){
ans.add(x);//没有死,添加到答案列表
}
for (String y:g.getOrDefault(x,Collections.emptyList())) {
//Collections 类的一个静态方法,返回一个不可变的空列表(List)对象。
dfs(y);
}
}