侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【二叉树, DFS】开幕式焰火

GabrielxD
2022-09-19 / 0 评论 / 0 点赞 / 17 阅读 / 334 字 / 正在检测是否收录...

题目

LCP 44. 开幕式焰火


「力扣挑战赛」开幕式开始了,空中绽放了一颗二叉树形的巨型焰火。
给定一棵二叉树 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

思路

维护一个哈希表(has)用于记录各种焰火的颜色有没有出现,一边遍历二叉树一遍更新哈希表,每出现一种新的焰火颜色就把计数增加,最后返回计数即可。

代码

class Solution {
    boolean[] has = new boolean[1001];

    public int numColor(TreeNode root) {
        if (root == null) return 0;
        int cnt = numColor(root.left) + numColor(root.right);
        if (!has[root.val]) {
            ++cnt;
            has[root.val] = true;
        }
        return cnt;
    }
}
class Solution {
    bool has[1001];

public:
    int numColor(TreeNode* node) {
        if (!node) return 0;
        int cnt = numColor(node->left) + numColor(node->right);
        if (!has[node->val]) {
            ++cnt;
            has[node->val] = true;
        }
        return cnt;
    }
};
0

评论区