題目描述

有兩位極客玩家參與了一場「二叉樹著色」的游戲。游戲中，給出二叉樹的根節(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；若無法獲勝，就請(qǐng)返回 false。

示例：

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

題目解析

明確獲勝的方式為占有n/2以上的節(jié)點(diǎn)，一號(hào)玩家所占有的節(jié)點(diǎn)，會(huì)把整個(gè)樹劃分為3個(gè)部分， 左子樹， 右子樹，根與其他。其中左右子樹數(shù)量通過遍歷即可得知，根與其他的數(shù)量為總節(jié)點(diǎn)減去左右子樹節(jié)點(diǎn)數(shù)，即p = n - l - r -1。當(dāng)這三部分中任一部分滿足獲勝條件即獲勝。

C++代碼

class Solution {
public:
    
    int leftNum = 0;
    int rightNum = 0;
    int dfs(TreeNode* node, int x) {
        if(node == NULL) return 0;
        int left = dfs(node->left, x);
        int right = dfs(node->right, x);
        if(node->val == x) {
            leftNum = left;
            rightNum = right;
        }
        return left + right + 1;
    }
    
    bool btreeGameWinningMove(TreeNode* root, int n, int x) {
        dfs(root, x);
        int p = n - leftNum - rightNum - 1;
        if(p > n/2 || leftNum > n/2 || rightNum > n/2) return true;
        return false;
    }
};