企业网站中文域名有必要续费吗,wordpress多级分销插件,昆山商城网站建设,广州地铁封闭最新消息每棵子树内缺失的最小基因值【LC2003】 有一棵根节点为 0 的 家族树 #xff0c;总共包含 n 个节点#xff0c;节点编号为 0 到 n - 1 。给你一个下标从 0 开始的整数数组 parents #xff0c;其中 parents[i] 是节点 i 的父节点。由于节点 0 是 根 #xff0c;所以 parent…每棵子树内缺失的最小基因值【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;}// 建树ListInteger[] g new ArrayList[n];Arrays.setAll(g, e - new ArrayList());for (int i 1; i n; i) {g[parents[i]].add(i);}SetInteger 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, ListInteger[] g, SetInteger 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 ) \mathcal{O}(n) O(n) n n n为二叉树的节点数目每个节点最多只会访问1次空间复杂度 O ( n m ) \mathcal{O}(nm) O(nm)
