LeetCode 1145. 二叉树着色游戏

2022-04-11 HGNULB 约 8 分钟

文章信息 6 个分类 3 个标签

分类

题目描述

✅ 1145. 二叉树着色游戏

题意分析

一棵有 n 个节点、节点值为 1 到 n 且互不相同的二叉树，n 是奇数。一号玩家先手，把值为 x 的节点涂红；二号玩家随后选一个未着色的节点涂蓝。此后双方轮流行动，每次只能把「自己已着色节点的相邻节点（父或左右子）」中尚未着色的一个涂成自己的颜色；无处可走就跳过。全部涂完后颜色多的一方获胜。问二号玩家是否存在必胜的首选点，存在则返回 true。

游戏规则里最关键的一句是只能从自己已有的领地向相邻节点扩张。这意味着着色过程本质上是两团颜色从各自起点向外蔓延，而一旦某个节点被对手先占据，它就成了一堵墙——蔓延无法穿过它。这把一道看似要做博弈搜索的题，变成了一道纯粹的图形分割题。

顺着这条线看红点 x：它把整棵树切成了三块互不连通的区域——x 的左子树、x 的右子树、以及树上除去 x 及其整棵子树后剩下的「父亲方向」部分。三块之间的任何通路都必须经过 x，而 x 已经是红色。

n 为奇数这个条件也不是装饰：它保证不会平局，最终一定有一方严格多于另一方，判胜条件可以干净地写成「某一方 > n/2」。

边界：x 可能就是根节点，此时父亲方向那块大小为 0；x 也可能是叶子，此时左右两块都是 0；n 可以是 1，此时二号玩家无处可下，必输。这三种情况都应该由统一的公式自然覆盖，不需要特判。

解法：统计三块区域大小

核心思路

先想暴力：枚举二号玩家的每一个可选点 y（共 n-1 个），对每种选择模拟整局博弈，看谁涂得多。模拟本身需要一次多源扩散，总代价 $O(n^2)$；更麻烦的是「模拟」这个词并不精确——双方都要走最优策略，写成搜索还要考虑决策顺序。瓶颈在于把它当成了博弈问题。

关键观察让博弈搜索消失：每一块与 x 都只有一个相邻的入口节点——左孩子、右孩子或父节点。二号玩家若选择某块的入口，入口立即变蓝；红色从 x 进入该块的唯一路径就被堵住，因此蓝色最终能染完整块。

这里不能说“在块内随便选一点”都能拿下整块。若蓝点没有占住入口，红色下一步可能先染入口并进入同一块。二号玩家的最优首选点只能是三个实际存在的入口之一。

这同时给出上下界：选入口可以得到对应整块；而蓝点无论落在哪里都属于三块之一，且不可能穿过红色的 x 去取得另外两块。因此二号玩家最多、也恰好能取得三块中的最大值，问题退化为比较三块大小。

于是问题只剩下算三个数。设 x 的左子树大小为 $L$、右子树大小为 $R$，则父亲方向的大小为
\[P = n - L - R - 1\]
减 1 是扣掉 x 自己。这一步用总数相减，省掉了「向上遍历」的麻烦——树只有父指向子的边，从 x 往上数节点并不方便，而总数已知就可以直接倒推。

判胜条件：只要 $\max(L, R, P) > n/2$（n 为奇数，整数除法下 n/2 等于 $\lfloor n/2 \rfloor$，> n/2 即「严格超过一半」），二号玩家就获胜。

求 $L$ 与 $R$ 只需一次后序遍历：递归函数 count(node) 的语义固定为返回以 node 为根的子树节点数，在回溯时若发现 node.val == x，就把此刻拿到的左右子树大小写入结果容器。递归返回值与附带记录各司其职，代码无需保存跨调用的成员状态。

解题步骤

定义递归语义：count(node) 返回以 node 为根的子树节点总数。空节点返回 0，这是递归基，同时天然覆盖了「x 是叶子」的情况——此时左右调用都返回 0。

后序处理：先递归左右孩子拿到 left 与 right，再处理当前节点。必须是后序——只有子树都数完了，才能在 node.val == x 时把 $L$、$R$ 记下来。前序或中序此时还拿不到完整的子树大小。

命中 x 时记录：if (node.val == x) { sizes[0] = left; sizes[1] = right; }。因为节点值互不相同，这个分支在整次遍历中只会触发一次。

返回子树大小：return left + right + 1。加 1 是算上自己，这是子树计数的标准式子。

倒推父亲方向：parent = n - sizes[0] - sizes[1] - 1。用全局总数减去两棵子树和 x 自己，避免向上遍历。

取三块最大值并判胜：max(parent, max(sizes[0], sizes[1])) > n / 2。用 > 而不是 >=：n 是奇数，n/2 向下取整后，> n/2 才等价于「超过半数」。

例如层序 [1,2,3,4,5,6,7,8,9,10,11]、n = 11、x = 3：节点 3 的左右子树各有 1 个节点，所以 $L=1$、$R=1$、$P=8$。父节点 1 是最大块的入口，二号玩家选择它可获得 8 个节点；8 > 11/2，返回 true。

再看 n = 3、x = 1、树为根 1 带两个孩子 2 和 3：$L = 1$、$R = 1$、$P = 3-1-1-1 = 0$，最大块是 1，而 n/2 = 1，1 > 1 不成立，返回 false——蓝色最多拿 1 个，红色拿 2 个。这里若把判胜写成 >=，就会错误地返回 true。

代码实现

class Solution {
    public boolean btreeGameWinningMove(TreeNode root, int n, int x) {
        int[] sizes = new int[2];
        count(root, x, sizes);
        // 父亲方向用总数倒推，省掉向上遍历。
        int parent = n - sizes[0] - sizes[1] - 1;
        int max = Math.max(parent, Math.max(sizes[0], sizes[1]));
        return max > n / 2;
    }

    // 返回以 node 为根的子树节点数；后序回溯时顺手记下 x 的左右子树大小。
    private int count(TreeNode node, int x, int[] sizes) {
        if (node == null) {
            return 0;
        }
        int left = count(node.left, x, sizes);
        int right = count(node.right, x, sizes);
        if (node.val == x) {
            sizes[0] = left;
            sizes[1] = right;
        }
        return left + right + 1;
    }
}

func btreeGameWinningMove(root *TreeNode, n int, x int) bool {
	leftSize, rightSize := 0, 0

	// 返回以 node 为根的子树节点数；后序回溯时顺手记下 x 的左右子树大小。
	var count func(node *TreeNode) int
	count = func(node *TreeNode) int {
		if node == nil {
			return 0
		}
		left := count(node.Left)
		right := count(node.Right)
		if node.Val == x {
			leftSize = left
			rightSize = right
		}
		return left + right + 1
	}

	count(root)
	// 父亲方向用总数倒推，省掉向上遍历。
	parent := n - leftSize - rightSize - 1
	maxPart := parent
	if leftSize > maxPart {
		maxPart = leftSize
	}
	if rightSize > maxPart {
		maxPart = rightSize
	}
	return maxPart > n/2
}

复杂度分析

时间复杂度：$O(n)$，一次后序遍历访问每个节点恰好一次，节点内只做常数次加法与比较；最后的三数取最大是常数时间。

空间复杂度：$O(h)$，$h$ 为树高，来自递归调用栈；退化成链状时为 $O(n)$，平衡时为 $O(\log n)$。除两个记录变量外没有额外结构。

关键点总结

看到「双方从各自领地向相邻位置蔓延、不能穿过对方」，先想割点与连通块而不是博弈搜索；本题二号玩家要选的是最大块与 x 相邻的入口，不是块内任意节点。

一个节点把二叉树切成三块——左子树、右子树、父亲方向，这是二叉树类题目里非常通用的分解视角。

父亲方向的大小用 n - L - R - 1 倒推，避免在只有向下指针的树上做向上遍历，这是「已知总量则算补集」的典型应用。

递归函数的返回值始终表示子树大小，sizes 只负责带出 x 的左右规模；局部结果避免了同一对象被重复调用时残留成员状态。

节点值互不相同保证命中分支只触发一次，写代码时可以放心不做「是否已记录」的保护。

n 为奇数使得「超过半数」等价于 > n/2（整数除法），条件必须用 > 而非 >=。

面试视角：这道题的分数几乎全在「说清楚为什么二号玩家能完整吃下所选区域」上。答题时要先讲「x 是三块之间唯一的通路且已被染红」，再给出「选最大块」的结论，最后才写那段十行的遍历代码——先讲清结构再写代码，比直接甩公式有说服力得多。

易错点总结

错误写法：判胜条件写成 max >= n / 2。用例 n = 3, x = 1、树为 1(2,3)：三块大小为 1、1、0，n/2 = 1，1 >= 1 成立返回 true，而正确答案是 false。

错误写法：父亲方向算成 n - leftSize - rightSize，忘了减去 x 自己。用例 n = 11, x = 3：P 算成 9 而不是 8，虽然本例结论未变，但当真实的 P 恰为 n/2 时会把败局误判成胜局。

错误写法：只比较左右子树，忘记父亲方向那一块。用例 n = 11, x = 3：只看 $L=1$、$R=1$，最大值 1 不超过 5，返回 false，而正确答案是 true——漏掉的正是最大的一块。

错误理解：认为蓝点落在最大块内任意位置都能占满该块。若 x 的左孩子是 u，蓝点却选了 u 的后代，红方下一步可先染 u，蓝方就无法越过 u；必须直接选择入口 u。

前序记录或计数漏掉当前节点：只在递归左右子树之前记录，或返回 left + right，都会让非叶子 x 的块大小错误。必须后序得到两边规模后再记录，并返回 left + right + 1。

额外特判根、叶子或 n=1：统一公式已经覆盖；例如 n=1 时三块都是 0，正确返回 false。

相似题目

题目	难度	考察点
104. 二叉树的最大深度	简单	后序返回子树信息的最小模板，本题的子树计数即由它演化而来
543. 二叉树的直径	简单	同为「递归返回值管子树、外部变量管答案」的双轨写法，返回深度而非大小
863. 二叉树中所有距离为 K 的结点	中等	也要处理「父亲方向」，但需显式建父指针而非用总数倒推
979. 在二叉树中分配硬币	中等	后序回溯时向上传递子树的盈亏差额，把结构信息压缩成一个返回值
877. 石子游戏	中等	同样是「看似博弈实为结论」的题，先手必胜可由奇偶性直接论证
486. 预测赢家	中等	真正需要博弈 DP 的版本，与本题对照可看出何时能把博弈退化成结论