LeetCode 1145. 二叉树着色游戏

约 5 分钟
文章信息 6 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 华为
标签
深度优先搜索 树 二叉树

题目描述

✅ 1145. 二叉树着色游戏

image-20260929074821153

image-20260929074821283

image-20260929074821389

题意分析

红方先选定值为 x 的节点，蓝方再选一个不同节点作为起点。之后红方先手，双方轮流把与自己已染色节点相邻的未染色节点占为己有；相邻包括父节点和左右孩子，不能穿过或改染对方节点。

无法继续染色的一方跳过回合，双方都不能操作时比较占有节点数。题目保证总数 n 为奇数，判断蓝方是否存在一个起点，可以确保最终占据严格超过半数的节点，而不是模拟某一组任意走法。

解法：统计三块区域大小

核心思路

[!blue]

树上两个节点之间只有一条简单路径。把已归红方的节点 x 当作不可通过的屏障，其他节点就分成至多三块：它的左子树、右子树，以及父节点方向的剩余部分。分别记大小为 L、R、P，其中 P = n - L - R - 1，减去的一对应红方已经占据的 x。

蓝方的起点必然落在其中一块，而且永远无法经过红色的 x 进入其他块，所以无论如何行动，蓝方能占有的节点数都不会超过这块的大小。这给出了胜利的必要条件：至少有一块严格大于全树的一半。

这个条件也足够。蓝方直接占据该区域与 x 相邻的入口：选择左孩子、右孩子或父节点。红方进入该区域的唯一路径就被这个蓝色入口挡住，无法争夺其中任何节点；蓝方则可以沿区域内的连接逐步染满整块。即使红方先手，也不能越过已经占据的入口，因此蓝方能保证得到整个区域。

所以不需要搜索每一回合，只要比较三块大小。用后序遍历让每个节点返回自身子树的节点数，在遇到 x 时顺手保存左右子树大小，父方向再通过总数补集求出。若三块最大值大于 n / 2，蓝方可获胜，否则任何起点都不够。

解题步骤

  1. 后序遍历二叉树，空节点返回零，非空节点返回左右子树大小之和再加一。
  2. 遍历到值为 x 的节点时，记录已经算好的左右子树大小。
  3. 计算父方向区域大小 n - L - R - 1。
  4. 取三块中的最大值，与整除后的 n / 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 为树高，来自递归调用栈；另外只保存左右区域大小。

关键点总结

[!green]

  • 红色起点把树切成三块，蓝方无法跨越这条屏障。
  • 选择紧邻 x 的区域入口，才能保证独占整块，而不是只在区域内部与红方竞争。
  • 父方向是左右子树和 x 之外的全部节点，不需要真正向上遍历。
  • 三块最大值既是蓝方可能得到的上界，也是通过正确起点能达到的值。

易错点总结

[!yellow]

  • 只比较左右子树，会漏掉最大的区域位于父节点方向的情况。
  • 计算补集时没有减去 x 自身，会把已属于红方的节点也计入蓝方领地。
  • 使用大于等于整除后的 n / 2，可能把不到半数的区域误判为足够获胜。
  • 在大区域内随意选一个节点，却声称一定得到整块，没有阻断入口时红方仍可能进入该区域。

相似题目

题目 难度 关联与区别
2049. 统计最高分的节点数目 中等 同样删除一个节点后按子树及父方向计算分量大小，原题将大小相乘，本题判断是否存在超过一半的可控制区域。
1110. 删点成林 中等 删掉对手初始节点后可从分出的连通区域理解可争夺范围，原题实际返回删除后的森林。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/60448789
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！