Leetcode 1145:二叉树着色游戏(超详细的解法!!!)
发布日期:2021-06-29 16:06:14
浏览次数:2
分类:技术文章
本文共 1166 字,大约阅读时间需要 3 分钟。
有两位极客玩家参与了一场「二叉树着色」的游戏。游戏中,给出二叉树的根节点 root
,树上总共有 n
个节点,且 n
为奇数,其中每个节点上的值从 1
到 n
各不相同。
游戏从「一号」玩家开始(「一号」玩家为红色,「二号」玩家为蓝色),最开始时,
「一号」玩家从 [1, n]
中取一个值 x
(1 <= x <= n
);
「二号」玩家也从 [1, n]
中取一个值 y
(1 <= 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
解题思路
这个问题有一定的技巧性,当我们玩家一操作后,实际上整颗树分成了三个部分。
此时我们的玩家二最佳操作只能获取这三个区域内最大的那块(点数最多的),那么问题就很简单了,只要三个区域中点数最多的那个大于n//2
即可。
class Solution: def btreeGameWinningMove(self, root: TreeNode, n: int, x: int) -> bool: c = [0, 0] def helper(node): if not node: return 0 l, r = helper(node.left), helper(node.right) if node.val == x: c[0], c[1] = l, r return l + r + 1 return helper(root) // 2 < max(max(c), n - sum(c) - 1)
reference:
我将该问题的其他语言版本添加到了我的
如有问题,希望大家指出!!!
转载地址:https://coordinate.blog.csdn.net/article/details/98479942 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
哈哈,博客排版真的漂亮呢~
[***.90.31.176]2024年04月18日 16时05分17秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
深度学习读书笔记之AE(自动编码AutoEncoder)
2019-04-30
深度学习读书笔记之RBM
2019-04-30
深度学习word2vec笔记之基础篇
2019-04-30
法国INRIA Data Sets & Images 数据集和图像库
2019-04-30
训练自己haar-like特征分类器并识别物体(1)
2019-04-30
iOS容易造成循环引用的三种场景,就在你我身边!
2019-04-30
有一个会做饭的女友是一种怎样的体验?
2019-04-30
Storm入门之第一章
2019-04-30
java提高篇之数组(1):认识JAVA数组
2019-04-30
java提高篇之数组(2)
2019-04-30
浅析数据一致性
2019-04-30
Java 多维数组遍历
2019-04-30
深入分析Java中的length和length()
2019-04-30
数据库连接池浅析
2019-04-30
Java面试参考指南——同步
2019-04-30
在Java中如何高效的判断数组中是否包含某个元素
2019-04-30
线程安全与共享资源
2019-04-30
八成Java开发者解答不了的问题
2019-04-30
关于Spring的69个面试问答——终极列表
2019-04-30