• Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.
  • This article also participated in the “Digitalstar Project” to win a creative gift package and creative incentive money.

Thank you very much for reading this article. Welcome [👍 like] [⭐ collect] [📝 comment] ~ Give up is not difficult, But insists it must be very cool ~ hope we all can be a little bit of progress every day ~ in this paper, from two headed white hat original ~ https://juejin.cn/user/2771185768884824/posts blog

LCP 44. Fireworks for the opening Ceremony:

The opening ceremony of the “Buckle Challenge” started with a huge fireworks in the shape of a binary tree. Given a binary tree root represents fireworks, the node value represents the color type of the position of the giant fireworks. Please help Xiao Kou calculate how many different colors the giant fireworks have.

Sample 1

Input: root = [1,3,2,1, NULL,2] Output: 3Copy the code

The sample 2

Input: root = [3,3,3] Output: 1 Description: Only one color appears in the fireworks, and the value is 3Copy the code

prompt

  • 1 <= Number of nodes <= 1000
  • 1 <= Node.val <= 1000

Analysis of the

  • There are several different values in the whole tree.
  • So the two aspects of knowledge, one is binary tree data structure, one is statistical counting.
  • The easiest thing to think of is a data structure like Set.
  • Loops and recursions work.
  • The hint already gives a range of node values, so you can use an array as an underlying data structure instead of a Set.
  • Count is determined by the number of nodes in the tree, and count is determined by the range of node values in the data structure.

Answer key

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); }}}Copy the code

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); }}Copy the code

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); }}};Copy the code

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
Copy the code

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
}
Copy the code

rust

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option
      
       >>,
      
// pub right: Option
      
       >>,
      
// }
//
// 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); }}}Copy the code

Portal: https://leetcode-cn.com/problems/sZ59z6/