1145 Binary Tree Coloring Game 二叉樹著色游戲

Description:
Two players play a turn based game on a binary tree. We are given the root of this binary tree, and the number of nodes n in the tree. n is odd, and each node has a distinct value from 1 to n.

Initially, the first player names a value x with 1 <= x <= n, and the second player names a value y with 1 <= y <= n and y != x. The first player colors the node with value x red, and the second player colors the node with value y blue.

Then, the players take turns starting with the first player. In each turn, that player chooses a node of their color (red if player 1, blue if player 2) and colors an uncolored neighbor of the chosen node (either the left child, right child, or parent of the chosen node.)

If (and only if) a player cannot choose such a node in this way, they must pass their turn. If both players pass their turn, the game ends, and the winner is the player that colored more nodes.

You are the second player. If it is possible to choose such a y to ensure you win the game, return true. If it is not possible, return false.

Example:

Example 1:

[圖片上傳失敗...(image-dbe9a7-1652434102541)]

Input: root = [1,2,3,4,5,6,7,8,9,10,11], n = 11, x = 3
Output: true
Explanation: The second player can choose the node with value 2.

Example 2:

Input: root = [1,2,3], n = 3, x = 1
Output: false

Constraints:

The number of nodes in the tree is n.
1 <= x <= n <= 100
n is odd.
1 <= Node.val <= n
All the values of the tree are unique.

題目描述:
有兩位極客玩家參與了一場「二叉樹著色」的游戲。游戲中，給出二叉樹的根節(jié)點(diǎn) root，樹上總共有 n 個(gè)節(jié)點(diǎn)，且 n 為奇數(shù)，其中每個(gè)節(jié)點(diǎn)上的值從 1 到 n 各不相同。

游戲從「一號(hào)」玩家開始（「一號(hào)」玩家為紅色，「二號(hào)」玩家為藍(lán)色），最開始時(shí)，

「一號(hào)」玩家從 [1, n] 中取一個(gè)值 x（1 <= x <= n）；

「二號(hào)」玩家也從 [1, n] 中取一個(gè)值 y（1 <= y <= n）且 y != x。

「一號(hào)」玩家給值為 x 的節(jié)點(diǎn)染上紅色，而「二號(hào)」玩家給值為 y 的節(jié)點(diǎn)染上藍(lán)色。

之后兩位玩家輪流進(jìn)行操作，每一回合，玩家選擇一個(gè)他之前涂好顏色的節(jié)點(diǎn)，將所選節(jié)點(diǎn)一個(gè) 未著色 的鄰節(jié)點(diǎn)（即左右子節(jié)點(diǎn)、或父節(jié)點(diǎn)）進(jìn)行染色。

如果當(dāng)前玩家無法找到這樣的節(jié)點(diǎn)來染色時(shí)，他的回合就會(huì)被跳過。

若兩個(gè)玩家都沒有可以染色的節(jié)點(diǎn)時(shí)，游戲結(jié)束。著色節(jié)點(diǎn)最多的那位玩家獲得勝利 ??。

現(xiàn)在，假設(shè)你是「二號(hào)」玩家，根據(jù)所給出的輸入，假如存在一個(gè) y 值可以確保你贏得這場游戲，則返回 true；若無法獲勝，就請返回 false。

示例 :

[圖片上傳失敗...(image-6facef-1652434102541)]

輸入：root = [1,2,3,4,5,6,7,8,9,10,11], n = 11, x = 3
輸出：True
解釋：第二個(gè)玩家可以選擇值為 2 的節(jié)點(diǎn)。

提示:

二叉樹的根節(jié)點(diǎn)為 root，樹上由 n 個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)上的值從 1 到 n 各不相同。
n 為奇數(shù)。
1 <= x <= n <= 100

思路:

模擬
要么將所有奇數(shù)位置減少到比相鄰偶數(shù)位置上的數(shù)少 1
要么將所有偶數(shù)位置減少到比奇數(shù)相鄰位置上的數(shù)少 1
除了兩端需要單獨(dú)考慮
分別求出奇數(shù)位置上和偶數(shù)位置上需要改變的數(shù)之和取較小的即可
時(shí)間復(fù)雜度為 O(n), 空間復(fù)雜度為 O(1)

代碼:
C++:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution 
{
private:
    int max_value = 0;
    
    int dfs(TreeNode* root, int x, int n)
    {
        if (!root) return 0;
        int l = dfs(root -> left, x, n), r = dfs(root -> right, x, n);
        if (root -> val == x) max_value = max({max_value, n - l - r - 1, l, r});
        return l + r + 1;
    }
public:
    bool btreeGameWinningMove(TreeNode* root, int n, int x) 
    {
        dfs(root, x, n);
        return max_value > n - max_value;
    }
};

Java:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private int max = 0;

    private int dfs(TreeNode root, int x, int n) {
        if (root == null) return 0;
        int l = dfs(root.left, x, n), r = dfs(root.right, x, n);
        if (root.val == x) max = Math.max(max, Math.max(n - l - r - 1, Math.max(l, r)));
        return l + r + 1;
    }

    public boolean btreeGameWinningMove(TreeNode root, int n, int x) {
        dfs(root, x, n);
        return max > n - max;
    }
}

Python:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def btreeGameWinningMove(self, root: Optional[TreeNode], n: int, x: int) -> bool:
        max_value = 0
        
        def dfs(cur: Optional[TreeNode]) -> int:
            nonlocal max_value
            if not cur:
                return 0
            left, right = dfs(cur.left), dfs(cur.right)
            if cur.val == x:
                max_value = max([max_value, left, right, n - left - right - 1])
            return left + right + 1
        dfs(root)
        return max_value > n - max_value