二叉树着色游戏【LC1145】

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

最开始时：

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

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

之后两位玩家轮流进行操作，「一号」玩家先手。每一回合，玩家选择一个被他染过色的节点，将所选节点一个 未着色 的邻节点（即左右子节点、或父节点）进行染色（「一号」玩家染红色，「二号」玩家染蓝色）。

如果（且仅在此种情况下）当前玩家无法找到这样的节点来染色时，其回合就会被跳过。

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

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

我再补！

DFS

• 思路：dfs+贪心

。找到可以染色的节点数最多的节点作为y ，记节点总数为n _y ，如果n _y > n _x ，那么结果为true；反之，为false

• 局部最优：二号玩家可以染色的节点数最多，一号玩家可以染色的节点数最少
• 全局最优：尽可能使二号玩家获胜

。那么y节点的可能性有三种：x 的父节点、左孩子节点、右孩子节点，该三棵子树的最大值，即为二号玩家可以染色的最大节点数n _y ，一号玩家可以染色的最小节点数即为n − n _y ，当n _y > n − n _y 即2 n _y > n 时，二号玩家可以获胜

n _y =max(left,right,n−left−right−1)

• 实现

使用dfs搜索三棵子树的大小，最后返回当n _y 最大时，2 n _y 是否可以大于n

class Solution {
    private int x, lsz, rsz;
    public boolean btreeGameWinningMove(TreeNode root, int n, int x) {
        this.x = x;
        dfs(root);
        return Math.max(Math.max(lsz, rsz), n - 1 - lsz - rsz) * 2 > n;
    }
    private int dfs(TreeNode node) {
        if (node == null) 
            return 0;
        int ls = dfs(node.left);
        int rs = dfs(node.right);
        if (node.val == x) {
            lsz = ls;
            rsz = rs;
        }
        return ls + rs + 1;
    }
}
作者：灵茶山艾府
链接：https://leetcode.cn/problems/binary-tree-coloring-game/solutions/2089813/mei-you-si-lu-yi-zhang-tu-miao-dong-pyth-btav/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

。复杂度

• 时间复杂度：O ( n )
• 空间复杂度：O ( n )

思考题

假如你是一号玩家，x 由你决定，你是否有必胜策略？

如果题目给的是一般的树呢（不是二叉树）？

见 树的重心。

把 x 选在重心上，一号玩家是必胜的。

作者：灵茶山艾府

链接：https://leetcode.cn/problems/binary-tree-coloring-game/solutions/2089813/mei-you-si-lu-yi-zhang-tu-miao-dong-pyth-btav/

来源：力扣（LeetCode）

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。