树节点着色最小颜色数求解：父子、同父级子节点不可同色

问题约束 #

计算满足以下两个规则的树节点着色最小颜色用量：

• 同一个父节点的所有子节点颜色不可重复
• 父节点和其直接子节点颜色不可重复

输入示例 #

边的数量 = 5
根节点 = 1
边列表：
1 2
1 4
2 3
3 5
4 6
该示例的正确输出结果为3。

原有代码问题 #

你当前编写的代码逻辑本质是统计树的总节点数，没有结合着色约束做计算，自然无法得到正确结果：

public static int process(int nodes, int root, int[][] edges) {
    int output = 0;
    Map<Integer, List<Integer>> map = new HashMap<>();
    for (int i = 0; i < edges.length; i++) {
        int key = edges[i][0];
        List<Integer> v = map.getOrDefault(key, new ArrayList<>());
        map.put(key, v);
        v.add(edges[i][1]);
    }

    Set<Integer> set = new HashSet<>();

    for (int k : map.keySet()) {
        List<Integer> list = map.get(k);
        if (set.add(k)) {
            output++;
        }
        for (int n : list) {
            if (set.add(n)) {
                output++;
            }
        }
    }
    return output;
}

正确解决思路 #

核心逻辑 #

该问题不需要做复杂的着色模拟，最小颜色数仅由树中单个节点的最大直接子节点数量决定：
假设某节点存在k个直接子节点，父节点本身需要占用1种颜色，k个子节点不能和父节点同色，且互相之间颜色不能重复，因此这部分最少需要k+1种颜色。整棵树的最小颜色数就是所有节点的最大子节点数加1。

示例验证 #

示例中各节点的直接子节点数分别为：

• 节点1：2个（子节点2、4）
• 节点2：1个（子节点3）
• 节点3：1个（子节点5）
• 节点4：1个（子节点6）
• 其余节点：0个
  最大子节点数为2，因此最小颜色数为2+1=3，和示例输出一致。

实现步骤 #

1. 根据输入的边列表构建树的存储结构，统计每个节点的直接子节点数量
2. 遍历所有节点，找到最大的子节点数值maxChildCnt
3. 返回结果为maxChildCnt + 1

内容的提问来源于stack exchange，提问作者Learner