[LeetCode] 1145. Binary Tree Coloring Game

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.

Example 2:

Input: root = [1,2,3], n = 3, x = 1
Output: false

Constraints:

• The number of nodes in the tree is n.
• 1 <= x <= n <= 100
• n is odd.
• 1 <= Node.val <= n
• All the values of the tree are unique.

二叉树着色游戏。

有两位极客玩家参与了一场「二叉树着色」的游戏。游戏中，给出二叉树的根节点 root，树上总共有 n 个节点，且 n 为奇数，其中每个节点上的值从 1 到 n 各不相同。

最开始时：

「一号」玩家从 [1, n] 中取一个值 x（1 <= x <= n）；
「二号」玩家也从 [1, n] 中取一个值 y（1 <= y <= n）且 y != x。
「一号」玩家给值为 x 的节点染上红色，而「二号」玩家给值为 y 的节点染上蓝色。

之后两位玩家轮流进行操作，「一号」玩家先手。每一回合，玩家选择一个被他染过色的节点，将所选节点一个 未着色 的邻节点（即左右子节点、或父节点）进行染色（「一号」玩家染红色，「二号」玩家染蓝色）。

如果（且仅在此种情况下）当前玩家无法找到这样的节点来染色时，其回合就会被跳过。

若两个玩家都没有可以染色的节点时，游戏结束。着色节点最多的那位玩家获得胜利 ✌️。

现在，假设你是「二号」玩家，根据所给出的输入，假如存在一个 y 值可以确保你赢得这场游戏，则返回 true ；若无法获胜，就请返回 false 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/binary-tree-coloring-game
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路是用 DFS 遍历整棵树，因为需要计算到底是玩家一还是玩家二可以得到更多的节点。

题意给的是一棵二叉树，并且给了二叉树中节点数量 n 和树中的一个 node，这个 node 是在树中的任意一个位置，你可以理解为是已经被玩家一染色过的某个 node。因为规则规定玩家只能对还未被遍历到的 node 染色，那么对于树中非 root 的任一 node 来说，如果这个 node 被玩家一染色了，那么玩家二只能在如下三种方案中选择一种来染色

• 往根节点走经过的所有 node
• 往当前 node 的左子树走，左子树所有 node 都可以被玩家二染色
• 往当前 node 的右子树走，右子树所有 node 都可以被玩家二染色

注意玩家二是没法穿过 node 去同时对比如左右子树同时染色的。

那么这道题具体的思路是先从根节点走，找到题目给的那个已经染色过的 node，然后计算这个 node 左子树的节点个数和右子树的节点个数。因为树里面一共有 n 个节点，那么从这个染色过的 node 往根节点的路径上存在的节点个数 = n - 1 - left - right。

时间O(n)

空间O(n)

Java实现

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode() {}
 8  *     TreeNode(int val) { this.val = val; }
 9  *     TreeNode(int val, TreeNode left, TreeNode right) {
10  *         this.val = val;
11  *         this.left = left;
12  *         this.right = right;
13  *     }
14  * }
15  */
16 class Solution {
17     TreeNode xNode;
18 
19     public boolean btreeGameWinningMove(TreeNode root, int n, int x) {
20         traverse(root, x);
21         int left = helper(xNode.left);
22         int right = helper(xNode.right);
23         if (left >= (n + 1) / 2) {
24             return true;
25         }
26         if (right >= (n + 1) / 2) {
27             return true;
28         }
29         int remain = n - 1 - left - right;
30         return remain >= (n + 1) / 2;
31     }
32 
33     private void traverse(TreeNode root, int x) {
34         if (root == null) {
35             return;
36         }
37         if (root.val == x) {
38             xNode = root;
39             return;
40         }
41         traverse(root.left, x);
42         traverse(root.right, x);
43     }
44 
45     private int helper(TreeNode root) {
46         if (root == null) {
47             return 0;
48         }
49         int left = helper(root.left);
50         int right = helper(root.right);
51         return left + right + 1;
52     }
53 }

LeetCode 题目总结