本文涉及知识点
LeetCode1519. 子树中标签相同的节点数
给你一棵树（即，一个连通的无环无向图），这棵树由编号从 0 到 n - 1 的 n 个节点组成，且恰好有 n - 1 条 edges 。树的根节点为节点 0 ，树上的每一个节点都有一个标签，也就是字符串 labels 中的一个小写字符（编号为 i 的 节点的标签就是 labels[i] ）
边数组 edges 以 edges[i] = [ai, bi] 的形式给出，该格式表示节点 ai 和 bi 之间存在一条边。
返回一个大小为 n 的数组，其中 ans[i] 表示第 i 个节点的子树中与节点 i 标签相同的节点数。
树 T 中的子树是由 T 中的某个节点及其所有后代节点组成的树。
示例 1：
输入：n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], labels = “abaedcd”
输出：[2,1,1,1,1,1,1]
解释：节点 0 的标签为 ‘a’ ，以 ‘a’ 为根节点的子树中，节点 2 的标签也是 ‘a’ ，因此答案为 2 。注意树中的每个节点都是这棵子树的一部分。
节点 1 的标签为 ‘b’ ，节点 1 的子树包含节点 1、4 和 5，但是节点 4、5 的标签与节点 1 不同，故而答案为 1（即，该节点本身）。
示例 2：
输入：n = 4, edges = [[0,1],[1,2],[0,3]], labels = “bbbb”
输出：[4,2,1,1]
解释：节点 2 的子树中只有节点 2 ，所以答案为 1 。
节点 3 的子树中只有节点 3 ，所以答案为 1 。
节点 1 的子树中包含节点 1 和 2 ，标签都是 ‘b’ ，因此答案为 2 。
节点 0 的子树中包含节点 0、1、2 和 3，标签都是 ‘b’，因此答案为 4 。
示例 3：
输入：n = 5, edges = [[0,1],[0,2],[1,3],[0,4]], labels = “aabab”
输出：[3,2,1,1,1]
提示：
1 <= n <= 105
edges.length == n - 1
edges[i].length == 2
0 <= ai, bi < n
ai != bi
labels.length == n
labels 仅由小写英文字母组成
后续DFS
m_ans[i][j] 记录以节点i为根的子树，包括字符’a’+j的数量。
显然：m_ans[i][j] = labels[i] == ‘a’+j。
然后累加： m_ans[next][j]，next是子节点。
封装类
用DFS 或BFS 获取各节点层次。然后将层次转成 leveNodes， leves[i] 包括所有层次为i的节点。
层次大的节点先处理。
代码
核心代码
class CNeiBo
{
public:
static vector<vector<int>> Two(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0)
{
vector<vector<int>> vNeiBo(n);
for (const auto& v : edges)
{
vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase);
if (!bDirect)
{
vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase);
}
}
return vNeiBo;
}
static vector<vector<std::pair<int, int>>> Three(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0)
{
vector<vector<std::pair<int, int>>> vNeiBo(n);
for (const auto& v : edges)
{
vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase, v[2]);
if (!bDirect)
{
vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase, v[2]);
}
}
return vNeiBo;
}
static vector<vector<int>> Mat(vector<vector<int>>& neiBoMat)
{
vector<vector<int>> neiBo(neiBoMat.size());
for (int i = 0; i < neiBoMat.size(); i++)
{
for (int j = i + 1; j < neiBoMat.size(); j++)
{
if (neiBoMat[i][j])
{
neiBo[i].emplace_back(j);
neiBo[j].emplace_back(i);
}
}
}
return neiBo;
}
};
class CBFSLeve {
public :
static vector<int> Leve(const vector<vector<int>>& neiBo, vector<int> start) {
vector<int> leves(neiBo.size(), -1);
for (const auto& s : start) {
leves[s] = 0;
}
for (int i = 0; i < start.size(); i++) {
for (const auto& next : neiBo[start[i]]) {
if (-1 != leves[next]) { continue; }
leves[next] = leves[start[i]] + 1;
start.emplace_back(next);
}
}
return leves;
}
template<class NextFun>
static vector<int> Leve(int N,NextFun nextFun, vector<int> start) {
vector<int> leves(N, -1);
for (const auto& s : start) {
leves[s] = 0;
}
for (int i = 0; i < start.size(); i++) {
auto nexts = nextFun(start[i]);
for (const auto& next : nexts) {
if (-1 != leves[next]) { continue; }
leves[next] = leves[start[i]] + 1;
start.emplace_back(next);
}
}
return leves;
}
static vector<vector<int>> LeveNodes(const vector<int>& leves) {
const int iMaxLeve = *max_element(leves.begin(), leves.end());
vector<vector<int>> ret(iMaxLeve + 1);
for (int i = 0; i < leves.size(); i++) {
ret[leves[i]].emplace_back(i);
}
return ret;
};
};
class Solution {
public:
vector<int> countSubTrees(int n, vector<vector<int>>& edges, string labels) {
auto neiBo = CNeiBo::Two(n, edges,false);
auto leves = CBFSLeve::Leve(neiBo, { 0 });
auto leveNodes = CBFSLeve::LeveNodes(leves);
vector<vector<int>> cnt(n, vector<int>(26));
vector<int> ans(n);
for (auto it = leveNodes.rbegin(); it != leveNodes.rend(); ++it) {
for (const auto& cur : *it) {
cnt[cur][labels[cur] - 'a']++;
for (const auto& next : neiBo[cur]) {
if (leves[next] < leves[cur]) { continue; }
for (int j = 0; j < 26; j++) {
cnt[cur][j] += cnt[next][j];
}
}
ans[cur] = cnt[cur][labels[cur] - 'a'];
}
}
return ans;
}
};
单元测试
int n;
vector<vector<int>> edges;
string labels;
TEST_METHOD(TestMethod11)
{
n = 7, edges = { {0,1},{0,2},{1,4},{1,5},{2,3},{2,6} }, labels = "abaedcd";
auto res = Solution().countSubTrees(n, edges, labels);
AssertEx({ 2,1,1,1,1,1,1 }, res);
}
TEST_METHOD(TestMethod12)
{
n = 4, edges = { {0,1},{1,2},{0,3} }, labels = "bbbb";
auto res = Solution().countSubTrees(n, edges, labels);
AssertEx({ 4,2,1,1 }, res);
}
TEST_METHOD(TestMethod13)
{
n = 5, edges = { {0,1},{0,2},{1,3},{0,4} }, labels = "aabab";
auto res = Solution().countSubTrees(n, edges, labels);
AssertEx({3,2,1,1,1 }, res);
}
扩展阅读
| 我想对大家说的话 |
|---|
| 工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。 |
| 学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作 |
| 有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注 |
| 闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
| 失败+反思=成功 成功+反思=成功 |
视频课程
先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
