2003. 每棵子树内缺失的最小基因值 DFS

2003. 每棵子树内缺失的最小基因值

有一棵根节点为 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：

输入：parents = [-1,0,0,2], nums = [1,2,3,4]
输出：[5,1,1,1]
解释：每个子树答案计算结果如下：
- 0：子树包含节点 [0,1,2,3] ，基因值分别为 [1,2,3,4] 。5 是缺失的最小基因值。
- 1：子树只包含节点 1 ，基因值为 2 。1 是缺失的最小基因值。
- 2：子树包含节点 [2,3] ，基因值分别为 [3,4] 。1 是缺失的最小基因值。
- 3：子树只包含节点 3 ，基因值为 4 。1是缺失的最小基因值。

示例 2：

输入：parents = [-1,0,1,0,3,3], nums = [5,4,6,2,1,3]
输出：[7,1,1,4,2,1]
解释：每个子树答案计算结果如下：
- 0：子树内包含节点 [0,1,2,3,4,5] ，基因值分别为 [5,4,6,2,1,3] 。7 是缺失的最小基因值。
- 1：子树内包含节点 [1,2] ，基因值分别为 [4,6] 。 1 是缺失的最小基因值。
- 2：子树内只包含节点 2 ，基因值为 6 。1 是缺失的最小基因值。
- 3：子树内包含节点 [3,4,5] ，基因值分别为 [2,1,3] 。4 是缺失的最小基因值。
- 4：子树内只包含节点 4 ，基因值为 1 。2 是缺失的最小基因值。
- 5：子树内只包含节点 5 ，基因值为 3 。1 是缺失的最小基因值。

示例 3：

输入：parents = [-1,2,3,0,2,4,1], nums = [2,3,4,5,6,7,8]
输出：[1,1,1,1,1,1,1]
解释：所有子树都缺失基因值 1 。

提示：

• n == parents.length == nums.length
• 2 <= n <= 1e5
• 对于 i != 0 ，满足 0 <= parents[i] <= n - 1
• parents[0] == -1
• parents 表示一棵合法的树。
• 1 <= nums[i] <= 1e5
• nums[i] 互不相同。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/smallest-missing-genetic-value-in-each-subtree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

做题结果

失败。这题dfs好想，但是想到有1的点才处理比较难

方法：dfs

1. 1如果存在只有1个

2. 如果不存在1那全填1

3. 如果存在1，那1到根只能占用树的至多一条路径，则不经1的点全都填1

4. 唯一含有1路径的路线dfs填充移动

class Solution {
      int[] ans;
      boolean[] hasOne;
      int one;
      public int[] smallestMissingValueSubtree(int[] parents, int[] nums) {
          int n = parents.length;
         Map<Integer,List<Integer>> map = new HashMap<>();
          for(int i = 1; i < n; i++){
              map.putIfAbsent(parents[i],new ArrayList<>());
              map.get(parents[i]).add(i);
          }
          hasOne = new boolean[n];
          int pos = -1;
          for(int i = 0; i < n; i++){
              if(nums[i]==1){
                  pos = i;
                  break;
              }
          }

          ans = new int[n];
          if(pos == -1){
              Arrays.fill(ans,1);
              return ans;
          }

          one = pos;
          hasOne[pos]=true;
          while (pos!=0){
              pos = parents[pos];
              hasOne[pos]=true;
          }


          for(int i =0; i < n; i++){
              if(!hasOne[i]) ans[i]=1;
          }
          fill(map,nums,one,parents);
          return ans;
      }

      Set<Integer> visited = new HashSet<>();
      int id = 1;
      private void fill(Map<Integer, List<Integer>> map, int[] nums, int index,int[] parents) {
          if(index==-1) return;
          if(map.containsKey(index)){
              add(map,nums,index);
          }else{
              visited.add(nums[index]);
          }
          for(;id<=nums.length+1;id++){
              if(!visited.contains(id)){
                  ans[index]=id;
                  break;
              }
          }
          fill(map,nums,parents[index],parents);
      }

      private void add(Map<Integer,List<Integer>> map, int[] nums, int index){
          visited.add(nums[index]);
          if(!map.containsKey(index)){
              return;
          }
          for(Integer next:map.get(index)){
              if(hasOne[next]) continue;
              add(map,nums,next);
          }
      }


  }