JZX轻语：简
LeetCode 1145 - 二叉树着色游戏
发表于2024年06月24日
该题目要求的是作为第二个选手，如何选择起始节点，使得必得节点数大于对手(该游戏为零和博弈，因此需要大于节点总数/2)。所谓得必得节点是指对手无法选择的节点。由题意不难推断，选手2的起始节点最优解在选手1的起始节点的父节点、左孩子或右孩子之中(可从源头尽可能阻断对手的选择)。当然为了递归的简洁，我们也可以通过后序遍历计算所有的必得节点数，取其中最大值即可。
如何计算子树的必得节点数：
如果该节点为
x，则以该节点为根的子树的必得节点数为0。否则，以该节点为根的子树的必得节点数为
1 + 左子树的必得节点数 + 右子树的必得节点数。
上述递归为啥正确呢，我们可以分情况讨论：
如果子树A中不包括选手1的起始点，此时我们可以选择该子树的根节点为起始点，通吃该子树的所有节点。注意，此时递归过程中的必得节点数为整棵子树的节点数。
如果子树A中包括选手1的起始点，且位于根的左子树L或右子树R中，此时最优解为选择选手1起始点的父节点，通吃选手1起始点子树以外的所有节点。不难得知，不包括在以选手1起始节点作为根的子树的节点个数的统计过程和上述递归相符。
class Solution:
def btreeGameWinningMove(self, root: Optional[TreeNode], n: int, x: int) -> bool:
max_points = 0
def get_points(node: Optional[TreeNode]) -> int:
nonlocal max_points
if node is None:
return 0
left_points = get_points(node.left)
right_points = get_points(node.right)
if node.val == x:
return 0
ensuring_points = 1 + left_points + right_points
max_points = max(max_points, ensuring_points)
return ensuring_points
get_points(root)
return max_points > n // 2