导航装置

/*
 * 题目思路：
 * 1. 给定一个二叉树结构的景区，每个节点代表一个景点。
 * 2. 要在若干景点设置导航装置，使得每个景点接收到的导航数据列表皆不相同。
 * 3. 最少需要设置多少个导航装置？
 * 4. 使用贪心算法，从叶子节点开始，尽量少设置装置，逐层向上保证所有节点的数据列表唯一。
 * 5. 使用Java Stream来简化某些集合操作。
 */

import java.util.*;
import java.util.stream.Collectors;

public class Solution {
    public int minNavigationDevices(TreeNode root) {
        if (root == null) return 0;
        Set<TreeNode> hasDevice = new HashSet<>();
        Set<TreeNode> covered = new HashSet<>();
        return dfs(root, hasDevice, covered) ? 1 : 2;
    }

    private boolean dfs(TreeNode node, Set<TreeNode> hasDevice, Set<TreeNode> covered) {
        if (node == null) return false;
        boolean leftCovered = dfs(node.left, hasDevice, covered);
        boolean rightCovered = dfs(node.right, hasDevice, covered);
        if (Stream.of(node.left, node.right)
            .filter(Objects::nonNull)
            .anyMatch(child -> !covered.contains(child))) {
            hasDevice.add(node);
            covered.add(node);
            Stream.of(node.left, node.right)
                .filter(Objects::nonNull)
                .forEach(covered::add);
            return true;
        }
        return hasDevice.contains(node);
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
}