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
分析
- 翻译一下题意就是看整个树里一共有几种不同的值。
- 所以考察了2个方面的知识点，一个是二叉树数据结构，一个是统计计数。
- 最容易想到的是用Set之类的数据结构。
- 循环和递归都可以。
- 提示中已经给定了节点值的范围，所以可以使用数组这种底层数据结构去替代Set等数据结构。
- 在遍历树的过程中判断计数，或者在最后再对计数的数据结构遍历计数，这两种方式都可以，在遍历树中判断计数受节点的数量影响，在最后再遍历计数数据结构计数受节点值取值范围影响。
题解
java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int numColor(TreeNode root) {
int ans = 0;
boolean[] flag = new boolean[1001];
dfs(root, flag);
for (boolean f : flag) {
if (f) {
ans++;
}
}
return ans;
}
private void dfs(TreeNode root, boolean[] flag) {
if (root != null) {
flag[root.val] = true;
dfs(root.left, flag);
dfs(root.right, flag);
}
}
}c
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
int numColor(struct TreeNode *root) {
int ans = 0;
bool flag[1001] = {false};
dfs(root, flag);
for (int i = 1; i < 1001; ++i) {
if (flag[i]) {
ans++;
}
}
return ans;
}
void dfs(struct TreeNode *root, bool *flag) {
if (root) {
flag[root->val] = true;
dfs(root->left, flag);
dfs(root->right, flag);
}
}c++
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int numColor(struct TreeNode *root) {
int ans = 0;
bool flag[1001] = {false};
dfs(root, flag);
for (bool f : flag) {
if (f) {
ans++;
}
}
return ans;
}
void dfs(struct TreeNode *root, bool *flag) {
if (root != nullptr) {
flag[root->val] = true;
dfs(root->left, flag);
dfs(root->right, flag);
}
}
};python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def numColor(self, root: TreeNode) -> int:
ans = 0
flag = [False] * 1001
def dfs(n):
if n:
flag[n.val] = True
dfs(n.left)
dfs(n.right)
dfs(root)
for f in flag:
if f:
ans += 1
return ansgo
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func numColor(root *TreeNode) int {
ans := 0
var flag [1001]bool
var dfs func(*TreeNode)
dfs = func(n *TreeNode) {
if n == nil {
return
}
flag[n.Val] = true
dfs(n.Left)
dfs(n.Right)
}
dfs(root)
for i := 1; i < 1001; i++ {
if flag[i] {
ans++
}
}
return ans
}rust
// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
pub fn num_color(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
let mut ans = 0;
let mut flag = vec![false; 1001];
Solution::dfs(root, &mut flag);
flag.into_iter().for_each(|f| {
if f { ans += 1; }
});
ans
}
fn dfs(root: Option<Rc<RefCell<TreeNode>>>, flag: &mut Vec<bool>) {
if let Some(root) = root {
let root = root.borrow();
flag[root.val as usize] = true;
Solution::dfs(root.left.clone(), flag);
Solution::dfs(root.right.clone(), flag);
}
}
}
原题传送门：https://leetcode-cn.com/problems/sZ59z6/
非常感谢你阅读本文~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://developer.aliyun.com/profile/sqd6avc7qgj7y 博客原创~
