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

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

做题结果

失败。这题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> 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 visited = new HashSet<>(); int id = 1; private void fill(Map> 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> 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); } } }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。