2024.4.7力扣每日一题——王位继承顺序

本文主要是介绍2024.4.7力扣每日一题——王位继承顺序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

2024.4.7

- - 题目来源
  - 我的题解
  - - 方法一哈希表+多叉树的前序遍历

题目来源

力扣每日一题；题序：1600

我的题解

方法一哈希表+多叉树的前序遍历

发现继承顺序的生成与多叉树的前序遍历一致，只需要在遍历过程中将已经去世的给排除就可以了。
如何存储继承关系？使用哈希表[父亲，儿子集合]
需要额外存储已经过世的人。注：有坑！！！！使用List要超时，只能使用Set

时间复杂度：

ThroneInheritance(kingName)：O(1)；
birth(parentName, childName)：O(1)；
death(name)：O(1)；
getInheritanceOrder()：O(n)，其中 n 是当前树中的总人数。需要对整棵树进行一次前序遍历，时间复杂度为 O(n)。
空间复杂度：O(n)。

class ThroneInheritance {Map<String,List<String>> parent;Set<String> hasDead;String king;public ThroneInheritance(String kingName) {king=kingName;parent=new HashMap<>();hasDead=new HashSet<>();}public void birth(String parentName, String childName) {if(!hasDead.contains(parentName)){List<String> l=parent.getOrDefault(parentName,new ArrayList<>());l.add(childName);parent.put(parentName,l);}}public void death(String name) {hasDead.add(name);}public List<String> getInheritanceOrder() {List<String> res=new ArrayList<>();dfs(king,res);return res;}public void dfs(String p,List<String> res){if(!hasDead.contains(p))res.add(p);for(String s:parent.getOrDefault(p,new ArrayList<>())){dfs(s,res);}}
}