jsp做网站开发,不属于网络营销的特点,厦门网站建设方案报价,全网营销全网推广1. 题意
给定一颗树#xff0c;求所有子树的最小基因值。 最小基因值定义为#xff0c;该树的所有节点组成的集合中未出现的最小正整数。
每颗子树内缺失的最小基因值
2. 题解
2.1 启发式合并
直接递归求出左右子树的所有可能值#xff0c;与根节点进行合并#xff0c…1. 题意
给定一颗树求所有子树的最小基因值。 最小基因值定义为该树的所有节点组成的集合中未出现的最小正整数。
每颗子树内缺失的最小基因值
2. 题解
2.1 启发式合并
直接递归求出左右子树的所有可能值与根节点进行合并注意始终是大集合合并小集合。即启发式合并。
一个小优化父节点的最小基因值必定大于等于子节点
class Solution {
public:vectorint smallestMissingValueSubtree(vectorint parents, vectorint nums) {int sz parents.size();vectorint res(sz, 1);vectorvectorint childs(sz);int kNode -1;for ( int i 0; i sz; i) {if ( parents[i] 0)childs[parents[i]].push_back(i);if ( nums[i] 1)kNode i;}vectorint vis(sz, 0);unordered_setint um;functionvoid(int) dfs [](int rt) {if (vis[rt])return;vis[rt] 1;um.insert(nums[rt]);for (int v:childs[rt])dfs(v);};int cnt 1;while ( kNode ! -1) {dfs(kNode);while ( um.count(cnt))cnt;res[kNode] cnt;kNode parents[kNode];}return res;}
};2.2 找出值为1的节点
实际上不难得出对于所有子节点不包含 1的树他们的最小基因值为1。
而对于以1为祖先节点的子节点来说他们的最小基因值也为1。
只需要考虑值为1的祖先节点的最小基因值所以我们可以先找到值为1的节点递归求出他的所有
子节点值集合自底向上求出祖先我们可以vis标记这个节点是否被求过来减少重复。
class Solution {
public:vectorint smallestMissingValueSubtree(vectorint parents, vectorint nums) {int sz parents.size();vectorint res(sz, 1);vectorvectorint childs(sz);int kNode -1;for ( int i 0; i sz; i) {if ( parents[i] 0)childs[parents[i]].push_back(i);if ( nums[i] 1)kNode i;}vectorint vis(sz, 0);unordered_setint um;functionvoid(int) dfs [](int rt) {if (vis[rt])return;vis[rt] 1;um.insert(nums[rt]);for (int v:childs[rt])dfs(v);};int cnt 1;while ( kNode ! -1) {dfs(kNode);while ( um.count(cnt))cnt;res[kNode] cnt;kNode parents[kNode];}return res;}
};
