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);}}
}

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~

这篇关于2024.4.7力扣每日一题——王位继承顺序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---