1145. Binary Tree Coloring Game #

Problem #

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.

Constraints:

• root is the root of a binary tree with n nodes and distinct node values from 1 to n.
• n is odd.
• 1 <= x <= n <= 100

Problem Summary #

Two geek players participate in a “binary tree coloring” game. In the game, the root node root of a binary tree is given. There are a total of n nodes in the tree, and n is odd. The values on the nodes are all distinct from 1 to n. The game starts with player “one” (player “one” is red, player “two” is blue). At the very beginning,

• Player “one” chooses a value x from [1, n] (1 <= x <= n);
• Player “two” also chooses a value y from [1, n] (1 <= y <= n) and y != x.
• Player “one” colors the node with value x red, while player “two” colors the node with value y blue.

After that, the two players take turns performing operations. In each round, a player chooses a node they have previously colored and colors one uncolored neighboring node of the chosen node (that is, the left child, right child, or parent). If the current player cannot find such a node to color, their turn is skipped. If neither player has any node they can color, the game ends. The player who colored the most nodes wins ✌️. Now, assuming you are player “two”, given the input, if there exists a value y that can ensure you win the game, return true; if you cannot win, return false.

Hints:

• The root node of the binary tree is root. The tree consists of n nodes, and the values on the nodes are all distinct from 1 to n.
• n is odd.
• 1 <= x <= n <= 100

Solution Ideas #

• 2 people participate in the binary tree coloring game. The number of nodes in the binary tree is odd. Player 1 and player 2 each choose a point on the binary tree to color. In each round, a player chooses a node they have previously colored and colors one uncolored neighboring node of the chosen node (that is, the left child, right child, or parent). When someone cannot choose a point to color, that turn is skipped. The game ends when neither side can continue coloring. The person who colors more nodes wins. Ask whether player two has a winning strategy?

• As shown in the figure, when player one chooses a red node, the binary tree may be split into 3 parts (connected components). If the chosen node is the root node, there may be 2 parts or 1 part; if the chosen node is a leaf node, there is 1 part. However, no matter which case it is, it does not matter. We can treat all cases as 3 parts. For example, if player one chooses a leaf node, we can also regard the left and right null pointers of the leaf node as two parts of size 0.
• So how should player two choose the blue node optimally? The answer is: choose the point closest to the red node and belonging to the connected component with the largest size. That is node 1 in the example figure. If we choose node 1 as the blue node, then the only nodes that can be colored red are node 6 and node 7, while blue can occupy the root node and its entire left subtree.
• Determining whether blue has a winning strategy can be converted into checking whether, among the three connected components cut by the red point, there exists a connected component whose size is greater than half of the total number of nodes. The process of counting the sizes of the three connected components can be implemented with depth-first search (DFS). When traversing to a certain node whose value is equal to the selected red node, we count the sizes of this node’s left subtree red_left and right subtree red_right; then we have already found the sizes of two connected components. The size of the last parent-node connected component can be obtained by subtracting these two connected component sizes and then subtracting the node occupied by red from the total number of nodes, namely parent = n - red_left - red_right - 1.

Code #

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
}