非常感謝你閱讀本文~
歡迎【👍點贊】【?收藏】【📝評論】~
放棄不難，但堅持一定很酷~
希望我們大家都能每天進步一點點~
本文由 二當家的白帽子 https://le-yi.blog.csdn.net/ 博客原創~

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/