LC version is slightly different: https://leetcode.com/problems/binary-tree-coloring-game
Two people in a game, player scores by claiming nodes in binary tree.
class TreeNode {
int val; // only used to uniquely identify a node
TreeNode parent;
TreeNode left;
TreeNode right;
// you can add more fields if you want
} The player who eventually owns more nodes wins the game.
Player A and B each claims a node at first.
After the first round, a player will only be able to claim a node adjacent to any node owned by himself.
A tree node is adjacent to its parent, left right and right child.
A node owned cannot be re-claimed.
End game when all nodes are owned.
If player A gets the first claim at node N, find whether it is possible for player B to win.
If yes, find out which node player B should claim at his first move.
Solution
The opponent's first move divides the tree into 3 components - left subtree, right subtree and parent branch of the node. Your best move is to claim a node adjacent to the opponent's node at the biggest component. Function countNodes() counts the sizes of 3 components. Function canWin() finds the largest component, whose size is your score.
public static boolean canWin(TreeNode root, TreeNode opponentMove) {
int parentSize = countNodes(opponentMove.parent, opponentMove); // size of parent component
int leftSize = countNodes(opponentMove.left, opponentMove); // size of left subtree component
int rightSize = countNodes(opponentMove.right, opponentMove); // size of right subtree component
int myScore = Math.max(Math.max(parentSize, leftSize), rightSize); // I take the biggest component
int treeSize = 1 + parentSize + leftSize + rightSize;
int opponentScore = treeSize - myScore; // opponent takes remaining nodes
System.out.print("my best score is " + myScore + "/" + treeSize + ". ");
if (myScore > opponentScore) {
TreeNode bestMove = myScore == parentSize ? opponentMove.parent : myScore == leftSize ? opponentMove.left : opponentMove.right;
System.out.println("my first move on " + bestMove.val);
}
return myScore > opponentScore;
}
private static int countNodes(TreeNode node, TreeNode ignore) {
if (node == null) return 0;
int count = 1;
if (node.parent != ignore) {
count += countNodes(node.parent, node);
}
if (node.left != ignore) {
count += countNodes(node.left, node);
}
if (node.right != ignore) {
count += countNodes(node.right, node);
}
return count;
}Follow-up:
If player B takes the first hand instead, which node should he pick?
Solution
To find the best move we must count the sizes of 3 adjacent components for every node in the tree. If exists a node whose biggest adjacent component is smaller than treesize / 2, the node is your best move, cuz your opponent won't be able to get a score higher than treesize / 2. In some cases there is no winning play, like on a tree with 2 nodes.
We can store the component sizes of every node in a 2-dimensional cache.
1st dimension: node
2nd dimension: which component (parent, left or right)
value: size of component
public static TreeNode bestMove(TreeNode root) {
if (root == null) return null;
if (root.left == null && root.right == null) return root;
// map stores size of every component
// each node at most has 3 components - to its left, to its right, to its top (parent)
// Map<node, Map<which component, size>>
Map<TreeNode, Map<TreeNode, Integer>> components = new HashMap<>();
TreeNode dummy = new TreeNode(-1);
dummy.left = root;
// calculate size of child components for all nodes
getComponentSize(dummy, root, components);
int treeSize = components.get(dummy).get(root);
for (TreeNode node : components.keySet()) {
int maxSize = 0; // maximum score possible for opponent
for (int size : components.get(node).values()) {
maxSize = Math.max(maxSize, size);
}
if (treeSize / 2.0 > maxSize) { // opponent cannot get half of the tree. You win.
return node; // best first move
}
}
return null; // no winning play
}
private static int getComponentSize(TreeNode n, TreeNode branch, Map<TreeNode, Map<TreeNode, Integer>> components) {
if (n == null || branch == null) return 0;
if (components.containsKey(n) && components.get(n).containsKey(branch)) {
return components.get(n).get(branch); // component size of a branch from node n (n excluded)
}
// a node n has 3 branches at most - parent, left, right
if (!components.containsKey(n)) {
components.put(n, new HashMap<>());
}
int size = 1; // 1 is the size of TreeNode branch
if (branch == n.left || branch == n.right) {
// size of the subtree 'branch' is size(branch.left) + size(branch.right) + 1
size += getComponentSize(branch, branch.left, components);
size += getComponentSize(branch, branch.right, components);
} else { //else when (branch == n.parent)
// see the tree from left-side or right-side view (see parent as a child; see one of the children as parent)
// size of the component is size(branch.parent) + size(branch.left/right child)
size += getComponentSize(branch, branch.parent, components);
size += branch.left == n ? getComponentSize(branch, branch.right, components) : getComponentSize(branch, branch.left, components);
}
components.get(n).put(branch, size); // cache the result of recursion
getComponentSize(n, n.parent, components); // calculate size of parent component for current node
return size;
}