leetcode 1145. 二叉树着色游戏

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

最开始时

「一号」玩家从 [1, n] 中取一个值 x1 <= x <= n
「二号」玩家也从 [1, n] 中取一个值 y1 <= y <= n且 y != x。
「一号」玩家给值为 x 的节点染上红色而「二号」玩家给值为 y 的节点染上蓝色。

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

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

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

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

 
示例 1

输入root = [1,2,3,4,5,6,7,8,9,10,11], n = 11, x = 3
输出true
解释第二个玩家可以选择值为 2 的节点。
示例 2

输入root = [1,2,3], n = 3, x = 1
输出false
 

提示

树中节点数目为 n
1 <= x <= n <= 100
n 是奇数
1 <= Node.val <= n
树中所有值 互不相同
通过次数21,885提交次数40,184

通过分析可知我们进行以下三种选择效果最佳。因为这三种情况分别最大程度地阻断了对方可染色的范围
选择x的父节点
选择x的左子节点
选择x的右子节点。
那么问题就转化为如何判断是否能够获胜这三种情况的获胜条件分别为
x所在的子树节点数 < n/2
x左子树节点数> n/2
x右子树节点数> n/2。
我们找到x所在的节点计算它左、右子树的节点个数进行判断即

作者marswiz
链接https://leetcode.cn/problems/binary-tree-coloring-game/solution/js-by-marswiz-oti1/
来源力扣LeetCode
著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} n
 * @param {number} x
 * @return {boolean}
 */
var btreeGameWinningMove = function(root, n, x) {
    let Xnode = getX(root, x)
    if (Xnode.left && count(Xnode.left) > n / 2) return true
    if (Xnode.right && count(Xnode.right) > n / 2) return true
     if (Xnode && count(Xnode)< n / 2) return true
     return false
};

function getX(node, x) {
    console.log('node', node, x)
    if(!node) return null
    if (x === node.val) return node
    return getX(node.left, x) ||  getX(node.right, x)
}

function count(node, Xnode) {
    if(!node) return 0
    return count(node.left) + count(node.right) + 1
}