package binarytree.numColor;

import binarytree.untils.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * 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
 */
public class numColor {
    /**
     * 遍历+去重
     * @param root
     * @return
     */
    public static int numColor(TreeNode root) {
        Map<Integer, Integer> map = new HashMap<>();
        preorder(root,map);
        return map.size();
    }

    private static void preorder(TreeNode root, Map<Integer, Integer> map) {
        if (root == null) {
            return;
        }
        if (map.containsKey(root.val)) {
            int count = map.get(root.val);
            map.put(root.val, ++count);
        } else {
            map.put(root.val, 1);
        }
        preorder(root.left, map);
        preorder(root.right, map);
    }

}