【算法】LCP 44. 开幕式焰火(java / c / c++ / python / go / rust)
【摘要】 LCP 44. 开幕式焰火:「力扣挑战赛」开幕式开始了,空中绽放了一颗二叉树形的巨型焰火。给定一棵二叉树 root 代表焰火,节点值表示巨型焰火这一位置的颜色种类。请帮小扣计算巨型焰火有多少种不同的颜色。 样例 1输入: root = [1,3,2,1,null,2] 输出: 3 解释: 焰火中有 3 个不同的颜色,值分别为 1、2、3 样例 2输入: root = [3,3,...
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 ans
go
/**
* 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://bbs.huaweicloud.cn/community/usersnew/id_1628396583336561 博客原创~
【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)