一、題目

有兩位極客玩家參與了一場「二叉樹著色」的游戲。游戲中，給出二叉樹的根節(jié)點(diǎn) root，樹上總共有 n 個(gè)節(jié)點(diǎn)，且 n 為奇數(shù)，其中每個(gè)節(jié)點(diǎn)上的值從 1 到 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)行操作，「一號(hào)」玩家先手。每一回合，玩家選擇一個(gè)被他染過色的節(jié)點(diǎn)，將所選節(jié)點(diǎn)一個(gè) 未著色 的鄰節(jié)點(diǎn)（即左右子節(jié)點(diǎn)、或父節(jié)點(diǎn)）進(jìn)行染色（「一號(hào)」玩家染紅色，「二號(hào)」玩家染藍(lá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 。

二、示例

示例 1 ：

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

示例 2 ：

【輸入】root = [1,2,3], n = 3, x = 1
【輸出】false

提示：

• 樹中節(jié)點(diǎn)數(shù)目為 n
• 1 <= x <= n <= 100
• n 是奇數(shù)
• 1 <= Node.val <= n
• 樹中所有值 互不相同

三、解題思路

根據(jù)題目描述，我們其實(shí)可以知道一號(hào)玩家是先手的，那么他第一次落子的位置，就決定著我們作為二號(hào)選手是否有機(jī)會(huì)能贏得比賽。我們以下圖中的節(jié)點(diǎn)為例，假設(shè)一號(hào)選手選擇了節(jié)點(diǎn)2這個(gè)位置落下了第一個(gè)棋子，那么如果二號(hào)選手選擇了節(jié)點(diǎn)3，那么我們就可以將整個(gè)樹節(jié)點(diǎn)劃分為如下3個(gè)區(qū)域，如下圖所示：

【區(qū)域1】公共待搶占區(qū)域：Node(1)
【區(qū)域2】一號(hào)玩家私有區(qū)域：Node(2)，Node(4)，Node(5)
【區(qū)域3】二號(hào)玩家私有區(qū)域：Node(3)，Node(6)，Node(7)

那么，我們對(duì)上面的邏輯清晰了之后，其實(shí)就可以得出一個(gè)解題思路，就是我們只需要根據(jù)一號(hào)選手第1次落子（firstNode）的位置來計(jì)算3種情況，即：

【情況1】二號(hào)選手落子在firstNode的左子節(jié)點(diǎn)上時(shí)，二號(hào)選手私有區(qū)域是否大于總數(shù)的一半。
【情況2】二號(hào)選手落子在firstNode的右子節(jié)點(diǎn)上時(shí)，二號(hào)選手私有區(qū)域是否大于總數(shù)的一半。
【情況3】二號(hào)選手落子在firstNode的根節(jié)點(diǎn)節(jié)點(diǎn)上時(shí)，二號(hào)選手私有區(qū)域是否大于總數(shù)的一半。

如果滿足上面的3個(gè)情況任意一種，則二號(hào)選手就有獲勝的可能了。那么，問題來了，為啥只關(guān)注了私有區(qū)域卻沒有關(guān)注公有區(qū)域呢？原因就是，因?yàn)?code>一號(hào)選手是先手的，他本來就在落子順序上占據(jù)了先機(jī)，那么對(duì)于占用公有區(qū)域的操作來說，一號(hào)選手也是具有先手的優(yōu)勢的。所以，對(duì)于二號(hào)選手的獲勝條件只能是，自己的私有區(qū)域要足夠的大。

解題思路說完了，下面我們就以例子來看一下，具體邏輯如下圖所示：

四、代碼實(shí)現(xiàn)

class Solution {
    int ltnc = 0, rtnc = 0;
    public boolean btreeGameWinningMove(TreeNode root, int n, int x) {
        nodeCount(root, x);
        return 2*ltnc > n || 2*rtnc > n || 2*(ltnc + rtnc + 1) < n;
    }
    public int nodeCount(TreeNode t, int v) {
        if (t == null) return 0;
        int lc = nodeCount(t.left, v);
        int rc = nodeCount(t.right, v);
        if (t.val == v) { // 找到x選擇的node，開始記錄這個(gè)node的左子樹和右子樹的節(jié)點(diǎn)個(gè)數(shù)
            ltnc = lc;
            rtnc = rc;
        }
        return lc + rc + 1;
    }
}

今天的文章內(nèi)容就這些了：

寫作不易，筆者幾個(gè)小時(shí)甚至數(shù)天完成的一篇文章，只愿換來您幾秒鐘的 點(diǎn)贊 & 分享 。

更多技術(shù)干貨，歡迎大家關(guān)注公眾號(hào)“爪哇繆斯” ~ \(^o)/ ~ 「干貨分享，每天更新」