[路飞]_1145. 二叉树着色游戏-一一网

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。

示例

输入：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

题解

x已经走第一步；y如果想赢需要染色节点超过x；也就是超过节点数目n的一半；

如何使y染色最多呢？一种思路，堵x

x下一步可以在x的左子节点或者右子节点或者父级节点3个方向染色；是不是可以计算这三个方向的节点数量；如果这三个方向的任意一个节点方向大于n/2；y就可以提前在这个方向染色，堵住x的去路从而获得胜利？

根据这个思路；第一步找到x所在的节点，第二步：找到x节点左侧子节点，右侧子节点，父级节点三个方向节点数量

返回答案

根据上述思路编辑代码如下：

完整代码

var btreeGameWinningMove = function(root, n, x) {
    const current = findNode(root,x)
    const leftNodeNum = getNodeNum(current.left)
    const rightNodeNum = getNodeNum(current.right)
    const hlaf = n/2;
    const diff = n - leftNodeNum - rightNodeNum - 1;
    if(leftNodeNum > hlaf || rightNodeNum > hlaf || diff > hlaf  ) return true;
    return false


    function findNode(node,x){
        if(node === null) return null;
        if(node.val === x) return node;
        const left = findNode(node.left,x)
        const right = findNode(node.right,x)
        return left !== null ? left : right
    }

    function getNodeNum (node){
        if(node === null) return 0;
        return getNodeNum(node.left) + getNodeNum(node.right) + 1

    }

};
复制代码