C++ | DFS | Top-Down Design
I like how other has the super fast bottom-up algorithm, but here is my top-down design.\n\nThe idea is running a dfs to recursively find the smallest number fo
I like how other has the super fast bottom-up algorithm, but here is my top-down design.\n\nThe idea is running a dfs to recursively find the smallest number for all subtrees except the subtree with one, and collected the path along with the information "sibling\'s smallest value". The smallest value for the rest of the tree is the missing smallest value of your subtree. So with the path and smallest sublings, we can construct the smallest missing value for the path from root to \'1\', and this is actually the only path that matters, all the rest can just be \'1\'.\n\nIt still runs in O(N), but not as fast as the bottom up version, it taks 1200ms.\n\n\n```\nclass Solution {\npublic:\n    vector<int> smallestMissingValueSubtree(vector<int>& parents, vector<int>& nums) {\n        map<int, vector<int>> tree;\n        int root = -1;\n        int n = parents.size();\n        \n        for (int i = 0; i < n; i++) {\n            if (parents[i] == -1) {\n                root = i;\n                continue;\n            }\n            tree[parents[i]].push_back(i);\n        }\n\n        vector<int> ans(n, 1);\n        set<int> temp(nums.begin(), nums.end());\n        int def = n+1;\n        if (*temp.rbegin() != n) {\n            // there is a missing value should be used default;\n            int prev = -1, now = -1;\n            auto it = temp.begin();\n            if (*it != 1) {\n                // special case\n                return ans;\n            }\n            prev = 1;it++;\n            while (it != temp.end()) {\n                now = *it;\n                if (prev + 1 != now) {\n                    def = prev+1;\n                    break;\n                }\n                prev = now;\n                it++;\n            }\n        }\n\n        vector<pair<int, int>> path; // <node, smallestSibling>\n        dfsFindOne(root, tree, ans, nums, path);\n\n        ans[root] = def;\n        int smv = min(def, nums[root]);\n        for (auto it = path.rbegin(); it != path.rend(); it++) {\n            smv = min(smv, it->second);\n            ans[it->first] = smv;\n            smv = min(smv, nums[it->first]);\n        }\n        return ans;\n    }\n\n    int dfsFindOne(int node, map<int, vector<int>> &tree, vector<int> &ans, vector<int>& nums, vector<pair<int, int>> &path) {\n        // return smallest value in node\'s subtree\n        if (tree.count(node) <= 0) {\n            // leaf\n            return nums[node];\n        }\n\n        if (nums[node] == 1) {\n            // node is in the middle but value = 1\n            return 1;\n        }\n\n        int hasOne = -1; // tree node\n        int smallestRet = INT_MAX;\n        for (int child : tree[node]) {\n            int ret = dfsFindOne(child, tree, ans, nums, path);\n            if (ret != 1 && ret < smallestRet)\n                smallestRet = ret;\n            if (ret == 1) {\n                hasOne = child;\n            }\n        }\n        if (hasOne != -1) {\n            path.push_back(make_pair(hasOne, smallestRet));\n            return 1;\n        }\n        return min(smallestRet, nums[node]);\n    }\n};\n```
[]