1145. Binary Tree Coloring Game

题目信息

题号:

1145

难度:

Medium

主题:

二叉树、区域划分、博弈

原题:

LeetCode 1145

重点:

第一名玩家先选择值为 x 的节点;第二名玩家选择另一节点后,双方只能从自己的已染色区域向相邻未染色节点扩展

题目重述

给定一棵含 n 个节点的二叉树,节点值为 1 到 n 且互不相同,n 为奇数。第一名玩家先把值为 x 的节点染成红色;第二名玩家随后选择另一个节点染成蓝色。

之后双方轮流行动,每次只能把与自己某个已染色节点相邻且尚未染色的节点染成自己的颜色;无法继续扩展时游戏结束,染色节点更多者获胜。请判断第二名玩家是否存在必胜的初始选择。

1 <= n <= 100 且 n 为奇数,1 <= x <= n,值为 x 的节点存在。

自建示例

选择父节点方向控制过半节点:

输入:root = [1,2,3,4,5,6,7], n = 7, x = 2
输出:true
解释:删除节点 2 后,包含根节点 1 的区域有 4 个节点。第二名玩家选择节点 1,即可控制超过半数节点并获胜。

三个节点时无法控制多数区域:

输入:root = [1,2,3], n = 3, x = 1
输出:false
解释:节点 1 两侧区域各只有一个节点,第二名玩家最多控制一个节点,不能超过第一名玩家。