发表于 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

• LC 题目链接