[Java] Easy to read solution
This solution is inspired by / based on https://leetcode.com/problems/smallest-missing-genetic-value-in-each-subtree/discuss/1641677/Java-Solution . \nI\'ve inc
This solution is inspired by / based on https://leetcode.com/problems/smallest-missing-genetic-value-in-each-subtree/discuss/1641677/Java-Solution . \nI\'ve included many comments, so it\'s easy to read / understand.\n\n```\nclass Solution {\n    \n    // "The idea is to find out the node whose genetic value is 1 and traverse up.\n    // All the rest of the subtrees have one missing."\n\t// quote from https://leetcode.com/problems/smallest-missing-genetic-value-in-each-subtree/discuss/1641677/Java-Solution\n    // For those subtrees containing 1, we\'ll maintain a sorted set of missing values, \n    // and reply with the smallest one\n    public int[] smallestMissingValueSubtree(int[] parents, int[] nums) {\n        int[] ans = new int[parents.length];\n        Arrays.fill(ans, 1); // respond with 1 for subtrees not containing 1\n        // create a map parent-->children\n        Map<Integer,List<Integer>> sonsMap = new HashMap<>();\n        for (int i=1; i<parents.length; i++) {\n            addSon(sonsMap, parents[i], i);\n        }\n        // find the node with value 1\n        int ind = -1;\n        for (int i=0; i<nums.length; i++) {\n            if (nums[i] == 1) {\n                ind = i;\n                break;\n            }\n        }\n        if (ind == -1) {\n            // no node with value 1 = it is the smallest missing from all subtrees\n            return ans;\n        }\n        // maintain a sorted set of all missing values from the subtree\n        SortedSet<Integer> missingValues = new TreeSet<>();\n        // init with missingValues [1 ... n+1]\n        // since we have n nodes, at least one of these values will be missing (we don\'t\n        // care about the actual values in nums, which might be out of this range)\n        for (int i=1; i<=nums.length+1; i++) {\n            missingValues.add(i);\n        }\n        // remove all values of descendents of node ind\n        removeDescendents(missingValues, sonsMap, nums, ind);\n        ans[ind] = missingValues.first();\n        // go up the tree, and calculate the smallest missing for subtrees containing ind\n        int parent = parents[ind];\n        while (parent != -1) {\n            missingValues.remove(nums[parent]);\n            // remove the other values in subtree rooted by parent\n            for (int son : sonsMap.get(parent)) {\n                if (son == ind) {\n                    continue; // we already removed thes subtree in previous steps\n                }\n                removeDescendents(missingValues, sonsMap, nums, son);\n            }\n            ans[parent] = missingValues.first();\n            ind = parent;\n            parent = parents[parent];\n        }\n        return ans;\n    }\n    \n    private static void removeDescendents(\n        SortedSet<Integer> missingValues, Map<Integer,List<Integer>> sonsMap,\n        int[] nums, int node) {\n        \n        missingValues.remove(nums[node]);\n        if (sonsMap.containsKey(node)) {\n            for (int son : sonsMap.get(node)) {\n                removeDescendents(missingValues, sonsMap, nums, son);\n            }\n        }\n    }\n    \n    private static void addSon(Map<Integer,List<Integer>> sonsMap, int parent, int son) {\n        List<Integer> sons = sonsMap.get(parent);\n        if (sons == null) {\n            sons = new ArrayList<>();\n            sonsMap.put(parent, sons);\n        }\n        sons.add(son);\n    }\n           \n}\n```
['Java']