[Swift]LeetCode1145. 二叉树着色游戏 | Binary Tree Coloring Game

发布时间:2021-07-27 06:16:00

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

Two players play a turn based game on a binary tree.? We are given?the?root?of this binary tree, and the number of nodes?n?in the tree.??n?is odd, and?each node has a distinct value from?1?to?n.


Initially, the first player names a value?x?with?1 <= x <= n, and the second player names a value?y?with?1 <= y <= n?and?y != x.? The first player colors the node with value?x?red, and the second player colors the node with value?y?blue.


Then, the players take turns starting with the first player.? In each turn, that player chooses a node of their color (red if player 1, blue if player 2) and colors an?uncolored?neighbor of the chosen node (either the left child, right child, or parent of the chosen node.)


If (and only if)?a player cannot choose such a node in this way, they must pass their turn.? If both players pass their turn, the game ends, and the winner is the player that colored more nodes.


You are the second player.? If it is possible to choose such a?y?to ensure you win the game, return?true.? If it is not possible, return?false.


Example 1:



Input: root = [1,2,3,4,5,6,7,8,9,10,11], n = 11, x = 3
Output: True
Explanation: The second player can choose the node with value 2.

Constraints:


root?is the root of a binary tree with?n?nodes and distinct node values from?1?to?n.1 <= x <= n?<= 100

有两位极客玩家参与了一场「二叉树着色」的游戏。游戏中,给出二叉树的根节点?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


Runtime:?12 ms


Memory Usage:?20.8 MB



1 /**
2 * Definition for a binary tree node.
3 * public class TreeNode {
4 * public var val: Int
5 * public var left: TreeNode?
6 * public var right: TreeNode?
7 * public init(_ val: Int) {
8 * self.val = val
9 * self.left = nil
10 * self.right = nil
11 * }
12 * }
13 */
14 class Solution {
15 func btreeGameWinningMove(_ root: TreeNode?, _ n: Int, _ x: Int) -> Bool {
16 var ls:Int = 0
17 var rs:Int = 0
18 dfs(root,x,&ls,&rs)
19 return max(max(ls,rs),n - ls - rs - 1) > (n>>1)
20 }
21
22 func work(_ root: TreeNode?) -> Int
23 {
24 if root == nil {return 0}
25 return work(root!.left) + work(root!.right) + 1
26 }
27
28 func dfs(_ root: TreeNode?,_ x:Int,_ ls:inout Int,_ rs:inout Int)
29 {
30 if root == nil {return}
31 if root!.val == x
32 {
33 ls = work(root!.left)
34 rs = work(root!.right)
35 }
36 else
37 {
38 dfs(root!.left,x,&ls,&rs)
39 dfs(root!.right,x,&ls,&rs)
40 }
41 }
42 }

?




转载于:https://www.cnblogs.com/strengthen/p/11297770.html






相关资源:着色问题c++实现

相关文档

  • Error: Checksum mismatch.
  • 从伤心到希望(对待友谊)
  • 蒙恬为什么最后怎么死的
  • 笔记本摄像头不好使怎么办
  • 2021考研英语:完型难题的解题技巧
  • 五年级关于保护环境演讲稿
  • 建筑安装工程承包合同书通用模板
  • 海思SDK中sample 代码VIO对ISP的ae和awb的使用流程
  • 有关初二英语教学计划范文
  • 简单理解一下JAVA中的日志
  • 高中古诗《夜雨寄北》鉴赏
  • 虎扑直男是什么意思
  • 新郎浪漫婚礼致辞精选
  • 路由器型号未适配是什么意思
  • 瞎折腾系列1-安装Windwos+Ubuntu双系统
  • 在工作中怎样和领导、同事沟通
  • 幼儿阅读能力的培养幼儿阅读能力的培养小议
  • 常用深度学习框架介绍
  • 一路上随行
  • 职业高中文明礼貌标语
  • swagger 返回json字符串_Swagger、knife4j和YApi
  • 形容老师关爱学生的佳句精选
  • 四年级写人作文:陶老师
  • 在浏览器输入 URL 回车之后发生了什么
  • 个人承包山林通用版合同
  • tf.keras损失函数总结
  • ubuntu下Mozilla Firefox安装flash插件
  • 蛋白粉的作用是什么?食用时需注意哪几点
  • 东芝电脑微电影营销,引领营销创新
  • 与爱情的个性签名
  • 猜你喜欢

  • 幼儿园2016年秋季开学后勤工作计划
  • 手机麦克风不可用怎么办
  • 2016年元旦小学活动方案
  • 新疆乌鲁木齐市高二数学上学期期末考试新人教A版
  • 【最新文档】采购员工作总结1000字word版本 (1页)
  • 陕西主要景点导游词
  • 2013南京会计继续教育考试答案1
  • 海图作业-评估
  • 孩子成长必读的经典书籍介绍
  • 2020年小升初语文模拟考试试卷外研版B卷 附答案
  • 【新版】酒店管理知识及商务礼仪
  • 内部控制评价报告(PPT41张)
  • 精美儿童学校安全教育课件
  • 襄阳市勘察设计执业单位及从业人员资料
  • 女性健康生活知识汇总
  • C/C++ VS2013 动态链接库详解
  • 买房不得不知的楼层风水禁忌
  • 东莞市天鹰万鹿实业投资有限公司企业信用报告-天眼查
  • 浅谈如何培养小学生诵读经典诗文的兴趣
  • 综合交通枢纽场站布局规划
  • 山东省临沂市中考历史复* 中国*现代史 第十一单元 中国*代经济和社会生活、科技和思想文化试题
  • 混凝土质量检测员上岗证考试多项选择题(2016-7-4)
  • 20xx年升旗仪式演讲稿格式范文三
  • 部编本2019-2020年度五年级语文上册第一单元:习作我的心爱之物课件
  • 【配套K12]七年级语文下册 第四单元 写作《怎样选材》教案 新人教版
  • 淘宝返利*台_淘宝返利网址
  • 保定烟囱拆除公司
  • 偶尔做白日梦有益身心健康
  • 兔子maya骨骼绑定_战神4角色绑定与过场动画制作
  • 【K12推荐】内蒙古包铁一中2018_2019学年高一政治上学期第二次月考试题(艺术)
  • 测试驱动开发TDD(Test Driven Development)和jasmine
  • 国际贸易比较优势和竞争优势问题的若干探讨(ppt29张)
  • 金星小叶紫檀木价格
  • 2018年春初二英语下册 Unit 2 I’ll help to clean up the city parks(第5课时)教学人教版
  • 我爱春天_小学作文_6
  • 人教版二年级上册认识时间ppt_图文-文档资料
  • 莫桑钻和钻石的区别莫桑钻和钻石有哪些区别
  • 【最新】精品教学资料-高一数学下学期期末考试试题理(11)
  • 母羊、狐狸和狼儿童故事
  • RHEL5安装oracle常见的错误 /opt/oracle/product/10.2.0/db_1/lib/network/lib/ins_net_client.mk
  • 【推荐K12】2018_2019学年高中地理课时分层作业2自然环境和人类活动的区域差异鲁教版必修3
  • python选择哪个版本-Python学习,要选哪个版本?
  • 电脑版