JAVA程序设计:二叉树着色游戏(LeetCode:1145)

有两位极客玩家参与了一场「二叉树着色」的游戏。游戏中,给出二叉树的根节点 root,树上总共有 n 个节点,且 n 为奇数,其中每个节点上的值从 1 到 n 各不相同。

 

游戏从「一号」玩家开始(「一号」玩家为红色,「二号」玩家为蓝色),最开始时,

「一号」玩家从 [1, n] 中取一个值 x(1 <= x <= n);

「二号」玩家也从 [1, n] 中取一个值 y(1 <= y <= n)且 y != x。

「一号」玩家给值为 x 的节点染上红色,而「二号」玩家给值为 y 的节点染上蓝色。

 

之后两位玩家轮流进行操作,每一回合,玩家选择一个他之前涂好颜色的节点,将所选节点一个 未着色 的邻节点(即左右子节点、或父节点)进行染色。

如果当前玩家无法找到这样的节点来染色时,他的回合就会被跳过。

若两个玩家都没有可以染色的节点时,游戏结束。着色节点最多的那位玩家获得胜利 ✌️。

 

现在,假设你是「二号」玩家,根据所给出的输入,假如存在一个 y 值可以确保你赢得这场游戏,则返回 true;若无法获胜,就请返回 false。

 

示例:

JAVA程序设计:二叉树着色游戏(LeetCode:1145)_第1张图片

输入:root = [1,2,3,4,5,6,7,8,9,10,11], n = 11, x = 3
输出:True
解释:第二个玩家可以选择值为 2 的节点。
 

提示:

二叉树的根节点为 root,树上由 n 个节点,节点上的值从 1 到 n 各不相同。
n 为奇数。
1 <= x <= n <= 100

思路:可以证明蓝色节点第一次一定要和红色节点相邻(要么是红色节点的父亲,要么是他的儿子),因为只有这样才能尽可能的堵住红色节点的扩张呀。而为了使蓝色节点尽可能的获胜,呢我们所选择的位置一定能够使得所划分到的节点数量尽可能多,因为只有三种位置的情况,我们从中找到最大值即可。

class Solution {

    private int n, x;
    private boolean flag;
    private Map count = new HashMap<>();

    public boolean btreeGameWinningMove(TreeNode root, int n, int x) {

        if (root.left == null && root.right == null)
            return false;

        this.n = n;
        this.x = x;
        flag = false;

        count.put(root, dfs(root));

        return flag;
    }

    private int dfs(TreeNode root) {

        if (root == null) return 0;

        int left = dfs(root.left);
        int right = dfs(root.right);

        count.put(root, left + right + 1);

        if (root.val == x) {
            int l = 0, r = 0;
            if (root.left != null) l += count.get(root.left);
            if (root.right != null) r += count.get(root.right);
            if (l > n / 2 || r > n / 2 || l + r + 1 <= n / 2) flag = true;
        }

        return left + right + 1;

    }

}

 

你可能感兴趣的