yeqiu

用户名：dotcpp0718185

访问量：2560

签　名：

永远相信美好的事情即将发生！

等　　级
排　　名	28358
经　　验	493
参赛次数	0
文章发表	3
年　　龄	20
在职情况	学生
学　　校	华中师范大学
专　　业	计算机科学与技术

　　自我简介：

算法小白一枚~

TA的其他文章

根据公式找规律
浏览：212

颜色平衡树（dfs后序遍历）
浏览：1472

你可能喜欢

C语言程序设计教程（第三版）课后习题10.1 （Java代码）

颜色平衡树（dfs后序遍历）

　　作者: yeqiu　　　　发表时间：2024-01-13 17:16:53 浏览：1472　|　评论：3　

原题链接：蓝桥杯2023年第十四届省赛真题-颜色平衡树

思路：

要判断每个子树是否为平衡树，需要统计子树的每种颜色的节点的数量，并判断所有数量是否相等。

对于一颗树的根节点，若该树的所有子树的统计结果都得到了，就可以直接将子树的统计结果累加，并加上根节点的颜色。因此可以使用dfs对树进行搜索，在后序遍历位置得到子树的统计结果并累加，就可以计算出该树的统计结果，判断所有颜色数量是否相等即可。

注意：统计结果cnt使用数组时，需要判断整颗树所有颜色的数量，而部分子树的颜色并不包含所有的颜色，每次判断的时间复杂度为O(num_c)，num_c为整棵树的颜色种数，这样会超时。因此可以使用map数据结构，这样每次只需判断子树所包含的颜色。

题解：
```c++
#include<iostream>
#include<vector>
#include<cstring>
#include<map>
using namespace std;
const int N = 2e5+1;

//最终结果
int ans=0;

//将子树的计数结果cnt_nb累加到根节点的结果cnt上
void add(map<int,int>& cnt,map<int,int>& cnt_nb){
    for(auto entry:cnt_nb){
        int c=entry.first,count = entry.second;
        cnt[c] += count;
    }
}

/*
对树进行dfs搜索，树的根节点为i，并返回该子树的各节点颜色计数结果
*/
map<int,int> dfs(vector<int>* g,int* c,int i){
    int sz = g[i].size();
    map<int,int> cnt; //记录子树的每个节点的各颜色节点的数量
    /*如果为叶子节点，直接返回*/
    if(sz==0){ 
        cnt[c[i]] = 1; 
        ans++; 
        return cnt;
    }
    
    /*如果不是叶子节点*/
    //将根节点的颜色加入cnt
    cnt[c[i]]=1;
    
    //遍历根节点的所有子树，并将子树的计数结果累加到cnt中
    for(int j=0;j<sz;j++){
        int nb = g[i][j];
        map<int,int> cnt_nb = dfs(g,c,nb);
        add(cnt,cnt_nb);
    } 
    
    //判断该子树的各种颜色节点的数量是否相等
    int count = cnt[c[i]];
    for(auto entry:cnt){
        //存在一种颜色数量不等，直接返回
        if(entry.second != count) return cnt; 
    }
    //各颜色的数量相等，结果+1
    ans++;
    
    //返回计数结果
    return cnt;
}

int main()
{
    int n;
    cin>>n;
    vector<int> g[N]; 
    int c[N]; //每个节点的颜色
    
    for(int i=0;i<n;i++){
        int f;
        cin>>c[i]>>f;
        
        if(f>=1){
            g[f-1].push_back(i); //记录节点f的子节点i（节点编号从0开始）
        }
    }
    
    dfs(g,c,0);
    cout<<ans;
    return 0;
}
```

0.0分

11 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

编程语言转换

万能编程问答

代码解释器

代码纠错

SQL生成与解释

　　评论区

累死自己卷死舍友

有一个答案过不了

2024-03-13 12:50:12

21savage

写的太好了!!!

2024-03-11 12:53:02

Kira

好难呜呜呜 乱七八糟的变量和函数名函数类型…

2024-03-04 21:04:22

yeqiu

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

C二级辅导-同因查找（C++代码）

交换Easy （C++代码）

C二级辅导-统计字符（C语言代码）

C语言程序设计教程（第三版）课后习题10.1 （Java代码）

颜色平衡树（dfs后序遍历）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题11.8 （C语言代码）

WU-输出九九乘法表（C++代码）

三角形（C++代码）记忆化搜索

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

Minesweeper （C语言描述，蓝桥杯）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

C二级辅导-统计字符（C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

yeqiu

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

C二级辅导-同因查找 （C++代码）

交换Easy （C++代码）

C二级辅导-统计字符 （C语言代码）

C语言程序设计教程（第三版）课后习题10.1 （Java代码）

颜色平衡树（dfs后序遍历）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题11.8 （C语言代码）

WU-输出九九乘法表 （C++代码）

三角形 （C++代码）记忆化搜索

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

Minesweeper （C语言描述，蓝桥杯）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

C二级辅导-统计字符 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C二级辅导-同因查找（C++代码）

C二级辅导-统计字符（C语言代码）

　　评论区

WU-输出九九乘法表（C++代码）

三角形（C++代码）记忆化搜索

C二级辅导-统计字符（C语言代码）