【每日一题Day364】LC2003每棵子树内缺失的最小基因值 | dfs

简介: 【每日一题Day364】LC2003每棵子树内缺失的最小基因值 | dfs

每棵子树内缺失的最小基因值【LC2003】

有一棵根节点为 0 的 家族树 ,总共包含 n 个节点,节点编号为 0 到 n - 1 。给你一个下标从 0 开始的整数数组 parents ,其中 parents[i] 是节点 i 的父节点。由于节点 0 是 根 ,所以 parents[0] == -1 。

总共有 105 个基因值,每个基因值都用 闭区间 [1, 105] 中的一个整数表示。给你一个下标从 0 开始的整数数组 nums ,其中 nums[i] 是节点 i 的基因值,且基因值 互不相同 。

请你返回一个数组 ans ,长度为 n ,其中 ans[i] 是以节点 i 为根的子树内 缺失 的 最小 基因值。

节点 x 为根的 子树 包含节点 x 和它所有的 后代 节点。

思路

本题关键点在于

如果树中不存在节点基因值为1的点,那么所有节点缺失的最小基因值为1

如果树中存在节点基因值为1的点,那么其祖先节点缺失的最小基因值不为1,其他节点均为1

那么,如果树中有基因值为1的节点的话,从该节点出发dfs求出其祖先节点缺失的最小基因值

dfs过程中使用哈希表记录目前已经遍历的基因值

使用变量记录当前缺失的最小基因值

实现

class Solution {
    public int[] smallestMissingValueSubtree(int[] parents, int[] nums) {
        int n = parents.length;
        int[] ans = new int[n];
        Arrays.fill(ans, 1);
        int node = -1;
        for (int i = 0; i < n; i++) {
            if (nums[i] == 1) {
                node = i; // 出发点
                break;
            }
        }
        if (node < 0) { // 不存在基因值为 1 的点
            return ans;
        }
        // 建树
        List<Integer>[] g = new ArrayList[n];
        Arrays.setAll(g, e -> new ArrayList<>());
        for (int i = 1; i < n; ++i) {
            g[parents[i]].add(i);
        }
        Set<Integer> vis = new HashSet<>();
        int mex = 2; // 缺失的最小基因值
        while (node >= 0) {
            dfs(node, g, vis, nums);
            while (vis.contains(mex)) { // node 子树包含这个基因值
                mex++;
            }
            ans[node] = mex; // 缺失的最小基因值
            node = parents[node]; // 往上走
        }
        return ans;
    }
    // 遍历 x 子树
    private void dfs(int x, List<Integer>[] g, Set<Integer> vis, int[] nums) {
        vis.add(nums[x]); // 标记基因值
        for (int son : g[x]) {
            if (!vis.contains(nums[son])) {
                dfs(son, g, vis, nums);
            }
        }
    }
}
作者:灵茶山艾府
链接:https://leetcode.cn/problems/smallest-missing-genetic-value-in-each-subtree/solutions/2505883/tu-jie-yi-zhang-tu-miao-dong-duo-chong-x-q095/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

复杂度

时间复杂度:O ( n ) ,n为二叉树的节点数目,每个节点最多只会访问1次

空间复杂度:O ( n + m )

相关文章
【最佳实践】宜搭的报表分析功能
“单据表单”和”流程表单”中提交的数据,可以在”报表页面”中作为数据源,进行进一步的分析。当一个表单中存在明细时,为了支持分析,宜搭进行了一些额外的处理。下面以一个具体场景(进货单)进行具体介绍
【最佳实践】宜搭的报表分析功能
停止使用云服务通常需要遵循以下步骤
停止使用云服务通常需要遵循以下步骤
664 2
2024年阿里云部署幻兽帕鲁(Palworld)新手教程:从零开始创建帕鲁服务器!
对于《幻兽帕鲁》的狂热粉丝来说,与好友联机畅玩无疑是加倍的快乐。但如何轻松搭建一个稳定的服务器,让游戏体验更加顺畅呢?今天,就为大家揭秘这一绝招——利用阿里云一键搭建《幻兽帕鲁》专属云服务器。
【阿里云云原生专栏】云原生下的API管理:阿里云API Gateway的应用场景与优势
【5月更文挑战第23天】阿里云API Gateway是高性能的API托管服务,适用于微服务API聚合、安全管理及流量控制。它提供统一入口、多种认证方式和流量控制策略,确保服务稳定性。具备高度可扩展性、丰富插件生态和简化API生命周期管理等特点。通过简单步骤,如创建API、配置后端服务、设置认证和发布,即可快速上手。作为云原生时代的API管理解决方案,阿里云API Gateway助力企业高效、安全地管理API,推动业务创新和数字化转型。
214 1
HR面试常问问题(上)
二、人事面试问题 第一题#请你自我介绍一下你自己?# 这道面试题是大家在以后面试过程中会常被问到的,那么我们被问到之后,该如果回答呢?是 说姓名?年龄?还是其他什么?
444 0
Flink CDC编译问题之增加依赖包失败如何解决
Flink CDC编译指的是将Flink CDC源代码转换成可执行程序的过程,可能会涉及到依赖管理和环境配置等问题;本合集将介绍Flink CDC编译的步骤、常见错误及其解决办法,以确保顺利完成编译过程。
Elasticsearch Serverless服务测评
阿里云检索分析服务 Elasticsearch 版是100%兼容开源的分布式检索、分析套件。提供ELK开源全托管的产品服务能力。为结构化/非结构化数据提供低成本、高性能及可靠性的检索、分析平台级产品服务。Serverless版本是基于云原生Serverless技术,为用户打造的更低成本、弹性灵活、开放兼容、开箱即用的云上Elasticsearch服务。

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等