二叉树着色游戏
难度:
标签:
题目描述
有两位极客玩家参与了一场「二叉树着色」的游戏。游戏中，给出二叉树的根节点 root，树上总共有 n 个节点，且 n 为奇数，其中每个节点上的值从 1 到 n 各不相同。
最开始时：
- 「一号」玩家从
[1, n]中取一个值x（1 <= x <= n）； - 「二号」玩家也从
[1, 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 <= 100n是奇数1 <= Node.val <= n- 树中所有值 互不相同
代码结果
运行时间: 19 ms, 内存: 16.1 MB
// 思路：
// 1. 使用Java Stream API简化节点计数过程。
// 2. 通过流式操作找到节点x，并计算其左子树、右子树及父节点的节点数量。
// 3. 返回结果。
import java.util.*;
import java.util.stream.*;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
private Map<TreeNode, Integer> nodeCounts = new HashMap<>();
private int countNodes(TreeNode node) {
if (node == null) return 0;
if (nodeCounts.containsKey(node)) return nodeCounts.get(node);
int count = 1 + countNodes(node.left) + countNodes(node.right);
nodeCounts.put(node, count);
return count;
}
public boolean btreeGameWinningMove(TreeNode root, int n, int x) {
TreeNode xNode = findXNode(root, x);
int leftCount = countNodes(xNode.left);
int rightCount = countNodes(xNode.right);
int parentCount = n - (leftCount + rightCount + 1);
int maxPart = IntStream.of(leftCount, rightCount, parentCount).max().orElse(0);
return maxPart > n / 2;
}
private TreeNode findXNode(TreeNode node, int x) {
if (node == null) return null;
if (node.val == x) return node;
TreeNode left = findXNode(node.left, x);
return (left != null) ? left : findXNode(node.right, x);
}
}
解释
方法:
该题解的核心思路是通过分析三个部分的节点数量来确定第二号玩家是否可以获胜。具体地，这三个部分是：1. 以x为根节点的子树的父节点及其祖先节点；2. x节点的左子树；3. x节点的右子树。如果其中任何一个部分的节点数超过总节点数的一半，那么第二号玩家选择该部分的任意一个节点作为初始着色点，都可以在游戏中取得优势。首先，代码通过层序遍历找到x节点并标记其父节点。然后，分别计算三个部分的节点数，并判断是否有超过总节点数一半的情况。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在层序遍历中，如何确保每个节点的父节点能被正确地记录和使用？
▷🦆
题解中提到的`num_parent`计算方式似乎有误，因为应该包括除`x`节点的子树外的所有节点。请问如何准确计算`x`节点的父节点及其祖先节点的数量？
▷🦆
递归函数`count_nodes`是否有考虑过优化以减少重复的节点计算，例如使用备忘录化的技术？
▷