深度优先 算法 leetcode 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 <= 节点个数 <= 1000

1<=节点个数<=1000

1

<

=

N

o

d

e

.

v

a

l

<

=

1000

1 <= Node.val <= 1000

1<=Node.val<=1000

解法：dfs + 哈希表

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

时间复杂度：

O

(

n

)

O(n)

O(n)

C++代码：

class Solution {

public:

unordered_set 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();

}

};

推荐阅读

 您阅读本篇文章共花了：