【每日一题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）
  著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
  

  • 复杂度
    • 时间复杂度：$\mathcal{O}(n)$，$n$为二叉树的节点数目，每个节点最多只会访问1次
    • 空间复杂度：$\mathcal{O}(n+m)$