1145. 二叉树着色游戏

ITCharge大约 5 分钟

---

1145. 二叉树着色游戏

标签：树、深度优先搜索、二叉树
难度：中等

题目链接

1145. 二叉树着色游戏 - 力扣

题目大意

描述：两个玩家轮流在一棵二叉树上染色。树有 $n$ 个节点，每个节点的值从 $1$ 到 $n$ 各不相同， $n$ 为奇数。

「一号」玩家先选一个值 $x$ ，把值为 $x$ 的节点染成红色。
「二号」玩家后选一个值 $y$ （ $y \ne x$ ），把值为 $y$ 的节点染成蓝色。

然后两位玩家轮流操作，「一号」先手。每回合，玩家选一个自己已经染色的节点，把它一个「未染色」的邻居（左子节点、右子节点、或父节点）染上自己的颜色。

如果某玩家没有可以染色的节点了，就跳过他的回合。当两个人都没有可染色的节点时游戏结束。染色节点多的玩家获胜。

要求：假设你是「二号」玩家，判断是否存在一个 $y$ 值，能让你稳赢这场比赛。能赢返回 true，否则返回 false。

说明：

树中节点数目为 $n$ 。
$1 \le x \le n \le 10^{3}$ 。
$n$ 是奇数。
$1 \le Node.val \le n$ 。
树中所有值互不相同。

示例：

示例 1：

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

示例 2：

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

解题思路

思路 1：抓住「切断」策略

这道题的关键在于理解「一号」玩家选了节点 $x$ 之后，二叉树就被 $x$ 分成了三个独立的部分：

$x$ 的左子树（以 $x$ 的左子节点为根的整棵子树）
$x$ 的右子树（以 $x$ 的右子节点为根的整棵子树）
$x$ 的父节点那边的剩余节点（除去 $x$ 和它的左右子树之外的所有节点）

用人话打个比方：想象 $x$ 是一个「关卡」，你（二号玩家）要做的就是「绕到关卡背后」——找一个节点落脚，让这个节点所在的区域足够大，然后你和一号玩家各自在自己的地盘里扩张，谁也过不去对方的地盘。

关键发现：

一旦一号玩家选了节点 $x$ ，他可以从 $x$ 出发向三个方向（左、右、父）染色。而你的最佳策略就是：选择这三个区域中最大的那个区域里的根节点（也就是紧挨着 $x$ 的那个节点），把它染成蓝色。

为什么选最大的区域？

因为你和一号玩家各自在自己的区域里扩张，互相碰不到（因为你们之间隔着一个对方的节点）。
你们三人只能在自己的区域里染色。所以只要你的区域节点数超过总节点数的一半，你就赢了。
由于 $n$ 是奇数，超过一半意味着大于 $n / 2$ 。

所以这个问题就简化为：

找到值为 $x$ 的节点。
数出它左子树有几个节点、右子树有几个节点。
计算出父节点那边还有几个节点： $n - 左子树节点数 - 右子树节点数 - 1$ （减去 $x$ 自己）。
看这三个数字中最大的那个是否大于 $n / 2$ 。如果大于，说明你能选一个足够大的区域来赢过一号。

为什么大于 $n / 2$ 就必胜？
因为你和一号玩家一旦各自选定了「地盘」，就再也不能进入对方的地盘了（通路被对方的节点锁死）。如果你占的地盘节点数超过一半，即使一号玩家把剩下一半全部占满，你也比他多。

思路 1：代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def btreeGameWinningMove(self, root: Optional[TreeNode], n: int, x: int) -> bool:
        # 用来记录 x 节点左子树和右子树的节点数
        self.left_count = 0
        self.right_count = 0
        
        # 深度优先搜索：计算以 node 为根的子树有多少个节点
        def count_nodes(node):
            if not node:
                return 0
            
            # 递归计算左右子树的节点数
            left = count_nodes(node.left)
            right = count_nodes(node.right)
            
            # 如果当前节点是 x，记录它的左右子树各自有多少节点
            if node.val == x:
                self.left_count = left
                self.right_count = right
            
            # 返回当前子树的总节点数（左 + 右 + 自己）
            return left + right + 1
        
        count_nodes(root)
        
        # 计算 x 的父节点那边的节点数（总节点数减去 x 及其左右子树）
        parent_count = n - self.left_count - self.right_count - 1
        
        # 如果三个区域中最大的那个超过了总节点数的一半，二号玩家就能赢
        max_part = max(self.left_count, self.right_count, parent_count)
        
        return max_part > n // 2

思路 1：复杂度分析

时间复杂度： $O(n)$ 。用人话说就是：整棵树有多少节点，我们就遍历一遍。每个节点只访问一次。
空间复杂度： $O(h)$ ，其中 $h$ 是树的高度。因为递归调用需要占用栈空间，树越高占用的空间越多。最坏情况 $h = n$ （一条直线），最好情况 $h = \log n$ （平衡树）。