Player 1 colors any node x first, and player 2 then colors any other uncolored node y adjacent to x. Once player 1 colors node x, the tree is logically split into 3 disjoint regions:
- Left subtree of
x - Right subtree of
x - Parent subtree of
x
[parent of x]
|
x
/ \
[left subtree] [right subtree]Play 2 can choose one of the 3 subtrees to color, and play 1 can only color the rest of the 2 subtrees. Player 2 will take over that chosen subtree, and player 1 will not be able to color any node in that chosen subtree by player 2.
So if player 2 chosen subtree > n / 2, then player 1 get < n / 2 nodes to color, and player 2 wins.
We just calculate the node of each subtree and identify the 3 choices for player 2.
private var xSum = 0
private var xLeftSum = 0
private var xRightSum = 0
fun btreeGameWinningMove(root: TreeNode?, n: Int, x: Int): Boolean {
val total = sum(root, x)
return (total - xSum) > n / 2 || xLeftSum > n / 2 || xRightSum > n / 2
}
private fun sum(root: TreeNode?, x: Int): Int {
if (root == null) return 0
val left = sum(root.left, x)
val right = sum(root.right, x)
val total = 1 + left + right
if (root.`val` == x) {
xSum = total
xLeftSum = left
xRightSum = right
}
return total
}