# LeetCode 1145. Binary Tree Col

@(LeetCode)

问题描述

有两个选手轮流玩一场游戏，其基于二叉树。给定一颗二叉树的根节点 root 和 节点总数 n，其中 n 是奇数，每个节点都是不同的值，范围是 1~n。

起初，第一个选手选定一个值 x，1 <= x <= n，第二个选手选定一个值 y，1 <= y <= n，且 y != x。第一个选手将 x 节点涂成红色，第二个选手将 y 节点涂成蓝色。

然后，从第一个选手开始，两个选手轮流进行游戏。在每一轮中，选手可以选择一个与其同色（选手 1 为红色，选手 2 为蓝色）节点相邻且未涂色的节点，即左/右节点，父节点均可。

如果一个选手不能选到这样的节点，则轮到另一个选手。如果两个选手都不能，则游戏结束，节点涂色最多的一方获胜。

栗 1：

image.png

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

想看英文原文的戳这里。

解题思路

题目有点长，精简一下，最终需要解决的问题为：

当选手 1 选择节点 x，选手 2 能否选择一个节点 y，使得最终的涂色节点数大于选手 1。

根据题中的游戏规则，选手可以任意选择一个与其颜色相同节点的相邻节点，但要求未涂色。比如选手 1 可以选择某一红色节点的相邻未涂色节点，选手 2 可以选择某一蓝色节点的相邻未涂色节点。

由于相邻节点的范围包括左右节点，父节点。所以某个选手在初始选择一个节点后，能够涂色的节点可以覆盖到与该节点关联的所有左右节点和父节点，只要节点没有被对方对手涂色。

举个栗子：

QQ20200411-212545@2x.png

选手 1 选择 x 后，所能涂色的节点为图中的所有红色节点。
选手 2 选择 y 后，所能涂色的节点为图中的所有蓝色节点。

因为玩游戏都想获胜，各个选手肯定想竭尽所能地将更多的节点涂上色。因此只需考虑选手 1 和选手 2 能涂色的最大节点数，将其进行对比，即可知道输赢。

假设选手 1 选择了 x，那么选手 2 需要阻止选手 1 涂更多的节点才可能获胜，所以最终选定的阻断节点应该是距 x 最近的节点，只可能为 x 的左节点、右节点和父节点。

• 若选择 x 的左节点，其能涂色的最大节点数 maxNodes = 以 x 的左节点开始的所有子节点数。
• 若选择 x 的右节点，其能涂色的最大节点数 maxNodes = 以 x 的右节点开始的所有子节点数。
• 若选择 x 的父节点，其能涂色的最大节点数 maxNodes = 节点总数 n - 以 x 开始的所有子节点数。

若 maxNodes > n - maxNodes，即maxNodes > n /2，则说明选手 2 能涂色的最大节点数大于选手 1，有可能获胜。

因此，我们只需要分别考虑到这三种情况，相应的计算出 maxNodes 进行比较即可。

我的解法

我处理的情况分得比较细，具体如下：

1. 如果 x 为根节点 root，那么选手 2 只能选择其左/右节点。

   首先计算出以 x 的左节点开始的节点总数 leftNodes。计算方式采用递归，详细代码可点此查看。

   • 如果左节点总数 > 剩余节点数，则取其左节点有可能。即 leftNodes > n / 2。
   • 如果右节点总数 > 剩余节点数，则取其右节点有可能。右节点总数 rightNodes = n - leftNodes - 1，同上判断 rightNodes > n / 2。

   节点数标识如下图所示：

   
   QQ20200411-211037@2x.png

2. 如果 x 不为根节点，那么选手 2 可以选择左/右节点，父节点。

   由于 x 只是一个节点值，我们需要找到其对应节点，才好计算出节点数。同样采用递归算法，详细代码可点此查看。

   • 若选择父节点，则先计算出以 x 开始的节点总数，剩余的则为选手 2 可涂节点数。
   • 若选择左/右节点，计算方法同 1。

   节点数标识如下图所示：

   
   QQ20200411-211525@2x.png

完整解法可点此查看。

更简洁的解法

分别计算出以 x 左节点开始的节点总数 left，右节点开始的节点总数 right。那么以 x 父节点开始的节点总数为 n - left - right - 1，取三者最大值与 n/2 进行比较。

这种解法比较巧妙的地方在于，只用遍历一次二叉树，就求得了 left 和 right。

求节点数的关键代码如下：

var count = function (node) {
  if (node) {
    const leftNodes = count(node.left)
    const rightNodes = count(node.right)

    // 计算节点值为 val 的左右子树节点总数，val 为 x
    if (node.val === val) {
      left = leftNodes
      right = rightNodes
    }

    return 1 + leftNodes + rightNodes
  }

  return 0
}

完整解法可点此查看。