柳州网站制作公司,中企动力做的网站,网站建设的初衷,山东莱芜最新新闻1. 题目
有两位极客玩家参与了一场「二叉树着色」的游戏。游戏中#xff0c;给出二叉树的根节点 root#xff0c;树上总共有 n 个节点#xff0c;且 n 为奇数#xff0c;其中每个节点上的值从 1 到 n 各不相同。
游戏从「一号」玩家开始#xff08;「一号」玩家为红色给出二叉树的根节点 root树上总共有 n 个节点且 n 为奇数其中每个节点上的值从 1 到 n 各不相同。
游戏从「一号」玩家开始「一号」玩家为红色「二号」玩家为蓝色最开始时 「一号」玩家从 [1, n] 中取一个值 x1 x n 「二号」玩家也从 [1, n] 中取一个值 y1 y n且 y ! x。 「一号」玩家给值为 x 的节点染上红色而「二号」玩家给值为 y 的节点染上蓝色。
之后两位玩家轮流进行操作每一回合玩家选择一个他之前涂好颜色的节点将所选节点一个 未着色 的邻节点即左右子节点、或父节点进行染色。
如果当前玩家无法找到这样的节点来染色时他的回合就会被跳过。
若两个玩家都没有可以染色的节点时游戏结束。着色节点最多的那位玩家获得胜利 ✌️。
现在假设你是「二号」玩家根据所给出的输入假如存在一个 y 值可以确保你赢得这场游戏则返回 true若无法获胜就请返回 false。
输入root [1,2,3,4,5,6,7,8,9,10,11], n 11, x 3
输出True
解释第二个玩家可以选择值为 2 的节点。提示
二叉树的根节点为 root树上由 n 个节点节点上的值从 1 到 n 各不相同。
n 为奇数。
1 x n 100来源力扣LeetCode 链接https://leetcode-cn.com/problems/binary-tree-coloring-game 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 计算节点个数
节点x相邻的3侧左子右子父侧各有多少节点二号玩家只能选择上面最多的一侧进行涂色邻接着x涂的最多
class Solution {TreeNode *nodeX NULL;int X;
public:bool btreeGameWinningMove(TreeNode* root, int n, int x) { X x;int count 0, numOfLeft 0, numOfRight 0, remaining, maxNodes;preOrder(root,count);//获取x对应的节点地址preOrder(nodeX-left,numOfLeft);//获取x左子的总数preOrder(nodeX-right,numOfRight);//获取右子的总数remaining n-1-numOfLeft-numOfRight;//剩余的父侧总节点数maxNodes max(remaining,max(numOfRight,numOfLeft));//最多的一侧return maxNodes n-maxNodes;//最多的一侧能赢吗}void preOrder(TreeNode* root, int num){if(root NULL)return;if(root-val X)nodeX root;num;preOrder(root-left,num);preOrder(root-right,num);}
};
