Hualiang

用户名：uq_23655448636

访问量：571

签　名：

nothing to say....

等　　级
排　　名	3044
经　　验	1975
参赛次数	0
文章发表	2
年　　龄	20
在职情况	学生
学　　校	四川农业大学
专　　业	计算机科学与技术

　　自我简介：

苦逼大学生....

TA的其他文章

树型结构 + DFS + 一点DP思想
浏览：502

你可能喜欢

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

2003年秋浙江省计算机等级考试二级C 编程题(2) （Java代码）

树型结构 + DFS + 一点DP思想

　　作者: Hualiang　　　　发表时间：2024-02-04 16:08:12 浏览：502　|　评论：0　

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

# 3144: 颜色平衡树

**该题解法并未优化，几乎是压线AC，重在思路。**

## 解题思路

因为该题是关于树的，所以可以先用多叉链表构建树型结构，以便于后续算法处理。
*p.s. 这里使用数组记录节点位置的话，可以更高效地创建树型结构*

int main() {
        int n, color, parent;
        cin >> n;
        cin >> color >> parent;
    
        TreeNode* root = new TreeNode(color);
        vector<TreeNode*> nodes = {NULL, root};
        unordered_map<int, int> colorCount;
    
        for (int i = 1; i < n; i++) {
            cin >> color >> parent;
            TreeNode* newNode = new TreeNode(color);
            nodes[parent]->children.push_back(newNode);
            nodes.push_back(newNode);
        }
        cout << dfs(root, colorCount); // 递归函数
        return 0;
    }

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

那么对于该树的每一个节点：

`以该节点为根节点的树的颜色平衡子树的个数` = 
`其左子树的颜色平衡子树的个数` +
`其右子树的颜色平衡子树的个数` +
`该树是否是颜色平衡树（是，则 + 1；否，则 + 0）`

看起来有点想动态规划的状态转移方程，但这里用DFS的后序遍历更容易实现，只需要实现一个递归函数，在每次递归时计算当前节点的颜色平衡子树的个数并将其作为返回值向上传递。而计算时判断该树是否是颜色平衡树，则使用哈希表来记录该树当前的颜色的数量，最后可以写个像下面这样的判断函数遍历一遍哈希表即可判断：

bool isBalance(unordered_map<int, int>& colorCount) {
        int res = colorCount.begin()->second;
        for (const auto &entry : colorCount) {
            if (res != entry.second) return false;
        }
        return true;
    }

因为是后序遍历，所以我们可以将哈希表作为函数的引用参数传递到后代的子节点中，每遍历一个子节点就记录其颜色，最后遍历到根节点时，以引用形式传递的哈希表就记录了该树所有的颜色的数量，如此即可判断该树是否是颜色平衡树。

**注意：**在递归函数中，向下传递哈希表时不能像下面这样直接传递：

int dfs(TreeNode* root, unordered_map<int, int>& colorCount) {
        int treeCount = 0;
        for (auto child : root->children) {
            treeCount += dfs(child, colorCount); // 这里直接将colorCount向下传递是错误的
        }
        colorCount[root->color]++;
        return treeCount + isBalance(colorCount);
    }

以该函数的一次递归为例，因为`colorCount`统计的是**以当前`root`节点为根节点的树**的颜色的数量。假设该`root`节点有两个子节点，也就是两棵子树，当第一次 for 循环后，也就是将第一颗子树遍历完后，`colorCount`就已经记录了第一颗子树的颜色信息；而接着在第二次 for 循环遍历第二颗子树中，直接向下传递哈希表，会导致`colorCount`仍然携带第一棵子树的颜色信息去遍历第二颗子树，而携带了不属于该子树的颜色信息显然会导致对该子树是否是颜色平衡树的判断出错。

因此，我们需要**新建一个空白哈希表来作为引用参数向下传递**，最后将其与`colorCount`合并即可，修改如下：

int dfs(TreeNode* root, unordered_map<int, int>& colorCount) {
        int treeCount = 0;
        for (auto child : root->children) {
            unordered_map<int, int> count; // 新建空白哈希表
            treeCount += dfs(child, count);
            for (const auto &entry : count) { // 合并
                colorCount[entry.first] += entry.second;
            }
        }
        colorCount[root->color]++;
        return treeCount + isBalance(colorCount);
    }

## 参考代码

#include <bits/stdc++.h>
    using namespace std;
    
    struct TreeNode {
        int color;
        vector<TreeNode*> children;
        TreeNode(int c) : color(c) {}
    };
    
    bool isBalance(unordered_map<int, int>& colorCount) {
        int res = colorCount.begin()->second;
        for (const auto &entry : colorCount) {
            if (res != entry.second) return false;
        }
        return true;
    }
    
    int f(TreeNode* root, unordered_map<int, int>& colorCount) {
        int treeCount = 0;
        for (auto child : root->children) {
            unordered_map<int, int> count;
            treeCount += f(child, count);
            for (const auto &entry : count) {
                colorCount[entry.first] += entry.second;
            }
        }
        colorCount[root->color]++;
        return treeCount + isBalance(colorCount);
    }
    
    int main() {
        int n, color, parent;
        cin >> n;
        cin >> color >> parent;
    
        TreeNode* root = new TreeNode(color);
        vector<TreeNode*> nodes = {NULL, root};
        unordered_map<int, int> colorCount;
    
        for (int i = 1; i < n; i++) {
            cin >> color >> parent;
            TreeNode* newNode = new TreeNode(color);
            nodes[parent]->children.push_back(newNode);
            nodes.push_back(newNode);
        }
        cout << f(root, colorCount);
        return 0;
    }

0.0分

7 人评分

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

编程语言转换

万能编程问答

代码解释器

代码纠错

SQL生成与解释

Hualiang

TA的其他文章

你可能喜欢

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

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

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

2003年秋浙江省计算机等级考试二级C 编程题(2) （Java代码）

（格式错误） qq290048663 碰巧告知我吧

树型结构 + DFS + 一点DP思想

评论区

精彩推荐

gets函数前有scanf读取时候，会读取缓存回车导致出错！！！

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

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

C语言程序设计教程（第三版）课后习题6.9 （C++代码）论pow函数的应用

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

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

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

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

字符串问题（C语言代码）

【简单计算】（C语言代码）

Hualiang

TA的其他文章

你可能喜欢

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

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

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

2003年秋浙江省计算机等级考试二级C 编程题(2) （Java代码）

（格式错误） qq290048663 碰巧告知我吧

树型结构 + DFS + 一点DP思想

评论区

精彩推荐

gets函数前有scanf读取时候，会读取缓存回车导致出错！！！

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

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

C语言程序设计教程（第三版）课后习题6.9 （C++代码）论pow函数的应用

C语言训练-求矩阵的两对角线上的元素之和 （C语言代码）

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

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

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

字符串问题 （C语言代码）

【简单计算】 （C语言代码）

　　评论区

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

字符串问题（C语言代码）

【简单计算】（C语言代码）