LCP 44. 开幕式焰火

题目链接

LCP 44. 开幕式焰火 easy

题目描述

「力扣挑战赛」开幕式开始了，空中绽放了一颗二叉树形的巨型焰火。

给定一棵二叉树 root代表焰火，节点值表示巨型焰火这一位置的颜色种类。

请帮小扣计算巨型焰火有多少种不同的颜色。

示例 1：

输入：root = [1,3,2,1,null,2]

输出：3

解释：焰火中有 3 个不同的颜色，值分别为 1、2、3

示例 2：

输入：root = [3,3,3]

输出：1

解释：焰火中仅出现 1 个颜色，值为 3

提示：

• $1<=节点个数<=1000$
• $1<=Node.val<=1000$

解法：dfs + 哈希表

用 dfs 遍历整棵树，用哈希表记录结点。最后返回哈希表的 size，即共有 size种不同的颜色。

时间复杂度： $O(n)$

C++代码：

class Solution {
public:unordered_set<int> uset;void dfs(TreeNode* root){if(root == nullptr) return;uset.insert(root->val);dfs(root->left);dfs(root->right);}int numColor(TreeNode* root) {dfs(root);return uset.size();}
};