Medium

题目描述

两位玩家在一棵二叉树上进行回合制游戏。给定这棵二叉树的根节点 root 和树中节点数 n。n 是奇数，每个节点都有从 1 到 n 的不同值。

最初，第一个玩家选择一个值 x（1 <= x <= n），第二个玩家选择一个值 y（1 <= 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
  • 树的所有值都是唯一的

提示：

  • 最佳选择 y 必须与 x 直接相邻，因为这样可以锁定该子树
  • 你能计算出与 x 相邻的（最多）3 个不同子树的大小吗？

解题思路

解题思路

这是一个博弈论问题。关键观察是：第二个玩家要想获胜，必须选择一个能够"切断"第一个玩家扩展路径的位置。

核心思路：

  1. 位置分析：第一个玩家选择节点 x 后，第二个玩家最优的策略是选择 x 的相邻节点（父节点、左子节点或右子节点），这样可以将树分割成不同的区域。

  2. 区域划分：以节点 x 为分界点，树被分为三个可能的区域：

    • x 的左子树
    • x 的右子树
    • 除 x 子树以外的其余部分（通过 x 的父节点连接）

  3. 获胜条件：第二个玩家要想获胜，需要控制超过一半的节点（即 > n/2 个节点）。如果第二个玩家选择了某个区域的入口，就能完全控制该区域。

  4. 策略：计算三个区域的大小，如果任意一个区域的大小超过 n/2，第二个玩家选择该区域就能获胜。

算法步骤：

  1. 通过 DFS 找到值为 x 的节点
  2. 计算该节点左子树和右子树的大小
  3. 计算剩余部分的大小（n - 左子树大小 - 右子树大小 - 1）
  4. 判断是否有任一区域大小超过 n/2

时间复杂度 O(n)，空间复杂度 O(h)，其中 h 是树的高度。

代码实现

class Solution {
private:
    int leftSize, rightSize;
    
    int dfs(TreeNode* node, int x) {
        if (!node) return 0;
        
        int left = dfs(node->left, x);
        int right = dfs(node->right, x);
        
        if (node->val == x) {
            leftSize = left;
            rightSize = right;
        }
        
        return left + right + 1;
    }
    
public:
    bool btreeGameWinningMove(TreeNode* root, int n, int x) {
        leftSize = rightSize = 0;
        dfs(root, x);
        
        int parentSize = n - leftSize - rightSize - 1;
        
        return max({leftSize, rightSize, parentSize}) > n / 2;
    }
};

class Solution:
    def btreeGameWinningMove(self, root: Optional[TreeNode], n: int, x: int) -> bool:
        self.left_size = 0
        self.right_size = 0
        
        def dfs(node):
            if not node:
                return 0
            
            left = dfs(node.left)
            right = dfs(node.right)
            
            if node.val == x:
                self.left_size = left
                self.right_size = right
            
            return left + right + 1
        
        dfs(root)
        parent_size = n - self.left_size - self.right_size - 1
        
        return max(self.left_size, self.right_size, parent_size) > n // 2

public class Solution {
    private int leftSize, rightSize;
    
    private int Dfs(TreeNode node, int x) {
        if (node == null) return 0;
        
        int left = Dfs(node.left, x);
        int right = Dfs(node.right, x);
        
        if (node.val == x) {
            leftSize = left;
            rightSize = right;
        }
        
        return left + right + 1;
    }
    
    public bool BtreeGameWinningMove(TreeNode root, int n, int x) {
        leftSize = rightSize = 0;
        Dfs(root, x);
        
        int parentSize = n - leftSize - rightSize - 1;
        
        return Math.Max(Math.Max(leftSize, rightSize), parentSize) > n / 2;
    }
}

var btreeGameWinningMove = function(root, n, x) {
    let leftSize = 0, rightSize = 0;
    
    function dfs(node) {
        if (!node) return 0;
        
        const left = dfs(node.left);
        const right = dfs(node.right);
        
        if (node.val === x) {
            leftSize = left;
            rightSize = right;
        }
        
        return left + right + 1;
    }
    
    dfs(root);
    
    const parentSize = n - leftSize - rightSize - 1;
    const maxSize = Math.max(leftSize, rightSize, parentSize);
    
    return maxSize > n / 2;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

项目复杂度
时间复杂度O(n)
空间复杂度O(h)

其中 n 是树中节点的数量，h 是树的高度。我们需要遍历整个树来找到目标节点并计算子树大小，递归调用栈的深度最坏情况下为树的高度。