LeetCode-Go 题解1145. Binary Tree Coloring Game 二叉树着色游戏的必胜策略【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本指南以 LeetCode-Go 仓库中 1145. Binary Tree Coloring Game 题解 为核心完整讲解「二叉树着色游戏」的规则、胜负判定原理与 Go 实现。读完本文你将掌握如何把一个博弈问题转化为「连通分量大小比较」问题并用一趟深度优先搜索DFS在 O(n) 时间内判断二号玩家是否存在必胜策略。题目回顾二叉树着色游戏的完整规则本题是 LeetCode 第 1145 题「Binary Tree Coloring Game」原题说明见 leetcode/1145.Binary-Tree-Coloring-Game/README.md。题目给出一个拥有n个节点的二叉树root其中n为奇数树上每个节点的值从1到n各不相同「一号」玩家先从[1, n]中取一个值x1 x n并把值为x的节点染成红色「二号」玩家从[1, n]中取一个值yy ! x并把值为y的节点染成蓝色之后两位玩家轮流行动每回合选择自己已着色节点的一个未着色邻节点左子节点、右子节点或父节点进行染色若某位玩家找不到可染色的邻节点则该回合跳过当双方都无法行动时游戏结束最终染色节点数量更多的一方获胜。题目要求假设你是二号玩家判断是否存在某个y值可以确保你赢得游戏若存在返回true否则返回false。约束条件root是含n个节点的二叉树的根n为奇数1 x n 100。示例推演以题目给出的示例为例Input: root [1,2,3,4,5,6,7,8,9,10,11], n 11, x 3 Output: true一号玩家把值为3的节点染成红色后二号玩家可以选择值为2的节点染成蓝色。这样一来蓝色阵营可以沿着节点 2 的子树和根结点方向持续扩张最终占据超过一半的节点从而锁定胜局。核心洞察红色节点把二叉树切割成三个连通分量解题思路的关键在于对游戏格局的几何观察推导过程详见 原题解当一号玩家选择了一个红色节点后这个节点会把整棵二叉树切割成三个部分连通分量红色节点的左子树红色节点的右子树红色节点的父节点方向即包含父节点、祖先节点以及可能存在的兄弟子树的部分。之所以可以统一看作三个部分是因为边界情况都能自然归并到该框架中如果一号玩家选择的是根节点那么它只有左、右两个子树此时父节点方向的连通分量大小为 0如果一号玩家选择的是叶节点那么它左右子树为空可以把左右两个空指针看作大小为 0 的两个连通分量。也就是说无论红色节点落在树的哪个位置都可以统一用「三个连通分量」来建模。必胜条件的推导占住最大连通分量即可取胜二号玩家如何选择蓝色节点才是最优策略答案是选择离红色节点最近、且所属连通分量规模最大的那个节点。以示例图见原题解为例红色节点 3 把树切成了左子树节点 2 及其子树、右子树节点 6、7和父节点方向节点 1 及其左子树三部分。二号玩家应选择节点 2红色节点左子树这个最大连通分量的边界节点染成蓝色后红色阵营能染色的范围被限制在红色节点 3 的右子树方向节点 6、7 及其后代蓝色阵营则可以把根结点 1、红色节点 3 的父节点方向以及整棵左子树全部占据。为什么这样一定能赢因为一旦二号玩家选定了某个连通分量中最靠近红色节点的节点染蓝那么红色节点所在的其余部分就与蓝色阵营彻底隔离——双方各自在一个连通分量内扩张互不干扰。游戏结束时蓝色阵营的节点数 所选连通分量的大小红色阵营的节点数 其余两个连通分量大小之和再加 1红色节点自身。因此二号玩家必胜当且仅当红色节点切分出的三个连通分量中存在一个分量的大小严格大于n / 2由于n为奇数大于一半即意味着超过红色阵营能获得的全部节点数。据此判断二号玩家能否获胜就等价于解决一个纯计数问题win ⟺ max(left, right, up) n / 2其中left、right分别是红色节点左、右子树的大小up是父节点方向连通分量的大小且满足恒等式up n - left - right - 1Go 源码实现解析仓库中的核心实现位于 leetcode/1145.Binary-Tree-Coloring-Game/1145. Binary Tree Coloring Game.go完整代码如下package leetcode import ( github.com/halfrost/LeetCode-Go/structures ) // TreeNode define type TreeNode structures.TreeNode func btreeGameWinningMove(root *TreeNode, n int, x int) bool { var left, right int dfsBtreeGameWinningMove(root, left, right, x) up : n - left - right - 1 n / 2 return left n || right n || up n } func dfsBtreeGameWinningMove(node *TreeNode, left, right *int, x int) int { if node nil { return 0 } l, r : dfsBtreeGameWinningMove(node.Left, left, right, x), dfsBtreeGameWinningMove(node.Right, left, right, x) if node.Val x { *left, *right l, r } return l r 1 }主函数一次遍历 三次比较主函数btreeGameWinningMove的逻辑非常紧凑分为三步调用 DFS 遍历整棵树同时统计出红色节点x的左子树大小left与右子树大小right利用恒等式up n - left - right - 1计算父节点方向连通分量的大小令n / 2得到半数阈值n为奇数整除 2 即向下取整等价于「大于一半」然后判断left n || right n || up n三者是否成立——只要任何一个连通分量超过半数二号玩家就有必胜策略。DFS 辅助函数后序遍历 命中记录辅助函数dfsBtreeGameWinningMove采用后序遍历先递归左右子树再处理当前节点巧妙地在一次遍历中同时完成两件事通过返回值l r 1向上累计子树大小使每个节点都能获知以自己为根的子树规模当遇到node.Val x时把刚算出的左右子树大小l、r写入left、right指针——这正是红色节点切割出的前两个连通分量。left、right通过指针传入是为了在递归过程中把「命中红色节点那一刻」的子树大小带出函数其余节点的子树大小仅作为返回值参与累加不产生额外副作用。TreeNode 与测试基建题目解中使用的TreeNode直接复用仓库统一的数据结构定义见 structures/TreeNode.gotype TreeNode struct { Val int Left *TreeNode Right *TreeNode }仓库通过 go.mod 中的replace github.com/halfrost/LeetCode-Go/structures ./structures将公共数据结构包本地化因此所有题解共享同一套树节点定义与构造工具例如Ints2TreeNode利用层序[]int构建二叉树和GetTargetNode按值查找节点它们位于 structures/TreeNode.go。复杂度与正确性分析时间复杂度O(n)。DFS 后序遍历每个节点恰好访问一次n 100的规模下单次调用开销极小空间复杂度O(h)其中h为树高即递归调用栈的最大深度最坏情况下链状树为 O(n)一般平衡树为 O(log n)。正确性方面可以把原博弈问题归纳为「连通分量占位」问题二号玩家只要抢先占据某个超过半数节点的连通分量即可确保最终染色节点数严格超过红色阵营而这道题判定过程仅依赖三个数值left、right、up它们在一次后序遍历中即可全部确定。测试用例验证仓库为该题提供了对应的单元测试 leetcode/1145.Binary-Tree-Coloring-Game/1145. Binary Tree Coloring Game_test.go其组织方式与仓库其他题解一致用para1145结构体封装输入参数root []int、n int、x int用ans1145结构体封装期望答案one bool通过structures.Ints2TreeNode(p.root)将层序数组转换为二叉树后调用主函数断言输出。测试覆盖了题目官方示例{ para1145{[]int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}, 11, 3}, ans1145{true}, },在仓库根目录执行go test ./leetcode/1145.Binary-Tree-Coloring-Game/即可运行该用例仓库的 gotest.sh 脚本则支持对全部题解执行覆盖率收集go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...便于统一验证。小结LeetCode 1145 是一道「博弈外壳、计数内核」的经典题目。透过 LeetCode-Go 的题解 可以看到这类轮流染色的树形博弈题往往可以通过分析「关键节点对连通分量的切割」降维成简单的统计问题二号玩家必胜 ⟺ 红色节点切出的某个连通分量大于总节点数的一半。掌握了「DFS 后序遍历 指针回传子树大小」这一实现套路你就能以 O(n) 时间、简洁的代码解决此类问题。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考