学院网站建设项目,怎样写企业网站建设方案,包头哪里做网站,dedecms导购网站模板二叉树着色游戏 提示 中等 199 相关企业 有两位极客玩家参与了一场「二叉树着色」的游戏。游戏中#xff0c;给出二叉树的根节点 root#xff0c;树上总共有 n 个节点#xff0c;且 n 为奇数#xff0c;其中每个节点上的值从 1 到 n 各不相同。
最开始时#xff1a;
「一…二叉树着色游戏 提示 中等 199 相关企业 有两位极客玩家参与了一场「二叉树着色」的游戏。游戏中给出二叉树的根节点 root树上总共有 n 个节点且 n 为奇数其中每个节点上的值从 1 到 n 各不相同。
最开始时
「一号」玩家从 [1, n] 中取一个值 x1 x n 「二号」玩家也从 [1, n] 中取一个值 y1 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 树中所有值 互不相同
题解
一开始就想复杂了以为是博弈论和动态规划然后静心下来想了下发现不是。。。。。
这个题目很简单因为是树结构如果是图结构就很复杂了树结构的特点就是一号玩家一开始选定的那个节点会把整棵树分成3个区间父节点的区间左子树的区间右子树的区间这3个区间互不相通。
于是问题简单化了二号玩家就是要去堵一号玩家的路于是问题又简化成了这3个区间哪个区间的节点数目最多如果数目能超过整个树一半的节点数目二号玩家就选择这个区间就赢了。
AC代码
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vectorintedge[105];int dfs(TreeNode* root){if(root-left!NULL){int left dfs(root-left);edge[root-val].push_back(left);edge[left].push_back(root-val);}if(root-right!NULL){int right dfs(root-right);edge[root-val].push_back(right);edge[right].push_back(root-val);}return root-val;}queueintq;bool vis[105];int bfs(int u, int x){memset(vis,0,sizeof(vis));vis[u] true;vis[x] true;q.push(u);int ans 0;while(!q.empty()){int u q.front();q.pop();ans 1;for(int i0;iedge[u].size();i){int v edge[u][i];if(vis[v])continue;vis[v] true;q.push(v);}}return ans;}bool btreeGameWinningMove(TreeNode* root, int n, int x) {dfs(root);for(int i0;iedge[x].size();i){int u edge[x][i];int ans bfs(u, x);if(ansint(n/2))return true;}return false;}
};
