本文涉及知识点
LeetCode2003. 每棵子树内缺失的最小基因值
有一棵根节点为 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 <= 105
对于 i != 0 ，满足 0 <= parents[i] <= n - 1
parents[0] == -1
parents 表示一棵合法的树。
1 <= nums[i] <= 105
nums[i] 互不相同。
深度优先搜索
除了基因1的节点及它的祖先，其它节点都缺少1。
DFS(cur)结束时，处理了且只处理了它哥哥及自己的后代，如果我们将基因1及其祖先调整成长子。可以将空间复杂从O(nlogn)降低到O(n)。
注意：如果不优化，空间复杂度是O(nn)，就是直接为每个节点分配空间，复制所有的后代。极端情况下，独子树的空间复杂度是O(nn)。直接用子树的空间，独子树空间复杂度O(n)；非独子树O(nlong)。
超时代码
class CParentToNeiBo { public: CParentToNeiBo(const vector<int>& parents) { m_vNeiBo.resize(parents.size()); for (int i = 0; i < parents.size(); i++) { if (-1 == parents[i]) { m_root = i; } else { m_vNeiBo[parents[i]].emplace_back(i); } } } vector<vector<int>> m_vNeiBo; int m_root=-1; }; class Solution { public: vector<int> smallestMissingValueSubtree(vector<int>& parents, vector<int>& nums) { CParentToNeiBo neiBo(parents); m_nums = nums; m_vIs1.resize(nums.size()); m_ans.assign(nums.size(),1); m_vHas.resize(100'000+10); DFS1(neiBo.m_root, neiBo.m_vNeiBo); for (auto& v : neiBo.m_vNeiBo) { for (int j = 1; j < v.size(); j++) { if (m_vIs1[v[j]]) { std::swap(v[0], v[j]); } } } DFS2(neiBo.m_root, neiBo.m_vNeiBo); return m_ans; } void DFS2(int cur, vector<vector<int>>& neiBo) { for (const auto& next : neiBo[cur]) { DFS2(next, neiBo); } m_vHas[m_nums[cur]] = true; while (m_vHas[m_iNeed]) { m_iNeed++; } if (m_vIs1[cur]) { m_ans[cur] = m_iNeed; } } bool DFS1(int cur, vector<vector<int>>& neiBo) { bool b = (1 == m_nums[cur]); for (const auto& next : neiBo[cur]) { b |= DFS1(next, neiBo); } return m_vIs1[cur]=b; } vector<int> m_nums,m_ans; vector<bool> m_vIs1; int m_iNeed = 1; vector<bool> m_vHas; };
1及其祖先不用DFS
class CParentToNeiBo { public: CParentToNeiBo(const vector<int>& parents) { m_vNeiBo.resize(parents.size()); for (int i = 0; i < parents.size(); i++) { if (-1 == parents[i]) { m_root = i; } else { m_vNeiBo[parents[i]].emplace_back(i); } } } vector<vector<int>> m_vNeiBo; int m_root=-1; }; class Solution { public: vector<int> smallestMissingValueSubtree(vector<int>& parents, vector<int>& nums) { CParentToNeiBo neiBo(parents); m_nums = nums; m_vIs1.resize(nums.size()); m_ans.assign(nums.size(),1); m_vHas.resize(100'000+10); int i1 = std::find(nums.begin(), nums.end(), 1)- nums.begin(); while ((-1 != i1) && (nums.size() != i1)) { m_vIs1[i1] = true; i1 = parents[i1]; } for (auto& v : neiBo.m_vNeiBo) { for (int j = 1; j < v.size(); j++) { if (m_vIs1[v[j]]) { std::swap(v[0], v[j]); } } } DFS2(neiBo.m_root, neiBo.m_vNeiBo); return m_ans; } void DFS2(int cur, vector<vector<int>>& neiBo) { for (const auto& next : neiBo[cur]) { DFS2(next, neiBo); } m_vHas[m_nums[cur]] = true; if (m_vIs1[cur]) { while (m_vHas[m_iNeed]) { m_iNeed++; } m_ans[cur] = m_iNeed; } } vector<int> m_nums,m_ans; vector<bool> m_vIs1; int m_iNeed = 1; vector<bool> m_vHas; };
测试用例
template<class T,class T2> void Assert(const T& t1, const T2& t2) { assert(t1 == t2); } template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { vector<int> parents, nums; { Solution sln; parents = { -1, 0, 0, 2 }, nums = { 1, 2, 3, 4 }; auto res = sln.smallestMissingValueSubtree(parents, nums); Assert({ 5,1,1,1 }, res); } { Solution sln; parents = { -1, 0, 1, 0, 3, 3 }, nums = { 5, 4, 6, 2, 1, 3 }; auto res = sln.smallestMissingValueSubtree(parents, nums); Assert({ 7,1,1,4,2,1 }, res); } { Solution sln; parents = { -1, 2, 3, 0, 2, 4, 1 }, nums = { 2, 3, 4, 5, 6, 7, 8 }; auto res = sln.smallestMissingValueSubtree(parents, nums); Assert({ 1,1,1,1,1,1,1 }, res); } }
2023年2月版（当时能过）
class Solution { public: vector smallestMissingValueSubtree(const vector& parents, const vector& nums) { m_c = nums.size(); m_vDirect.resize(m_c); for (int i = 1; i < parents.size(); i++) { m_vDirect[parents[i]].push_back(i); } m_vVisiteValue.resize(m_c + 1); m_vRet.assign(m_c, 1); for (int i = 0; i < nums.size(); i++) { if (1 == nums[i]) { DFS(i, -1,parents, nums); break; } } return m_vRet; } void DFS(int iCur, int iFromChild,const vector& parents, const vector& nums) { if (-1 == iCur) { return; } DFSForValue(iCur, iFromChild, nums); int iMiss = (-1 == iFromChild) ? 1 : m_vRet[iFromChild]; while ((iMiss < m_vVisiteValue.size()) && (m_vVisiteValue[iMiss])) { iMiss++; } m_vRet[iCur] = iMiss; DFS(parents[iCur], iCur, parents, nums); } void DFSForValue(int iCur, int iFromChild, const vector& nums) { m_vVisiteValue[nums[iCur]] = true; for (auto& next : m_vDirect[iCur]) { if (next == iFromChild) { continue; } DFSForValue(next, iFromChild, nums); } } int m_c; vector<vector> m_vDirect; vector m_vRet; vector m_vVisiteValue; };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 我想对大家说的话 |
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
