【LeetCode题解】1600. 王位继承顺序(前序遍历多分支树)

发布于:2024-04-08 ⋅ 阅读:(125) ⋅ 点赞:(0)


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

点击移步博客主页,欢迎光临~

偷cyk的图


网站公告

今日签到

点亮在社区的每一天
去签到