aboutsummaryrefslogtreecommitdiff
path: root/binary_tree_colouring_game.py
diff options
context:
space:
mode:
Diffstat (limited to 'binary_tree_colouring_game.py')
-rw-r--r--binary_tree_colouring_game.py48
1 files changed, 48 insertions, 0 deletions
diff --git a/binary_tree_colouring_game.py b/binary_tree_colouring_game.py
new file mode 100644
index 0000000..b2b42f7
--- /dev/null
+++ b/binary_tree_colouring_game.py
@@ -0,0 +1,48 @@
+# 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 colours the node with value
+'x' red and the second player colours 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 colour and the colours an uncoloured neighbour of the
+chose node.
+"""
+
+
+# Definition for a binary tree node.
+class TreeNode(object):
+ def __init__(self, val=0, left=None, right=None):
+ self.val = val
+ self.left = left
+ self.right = right
+
+
+class Solution(object):
+ def btreeGameWinningMove(self, root, n, x):
+ """
+ :type root: Optional[TreeNode]
+ :type n: int
+ :type x: int
+ :rtype: bool
+ """
+ c = [0, 0]
+
+ def cnt(node):
+ if not node:
+ return 0
+ l, r = cnt(node.left), cnt(node.right)
+ if node.val == x:
+ c[0], c[1] = l, r
+ return l + r + 1
+
+ return cnt(root) / 2 < max(max(c), n - sum(c) - 1)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.btreeGameWinningMove(root=[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11], n=11, x=3))
+ print(obj.btreeGameWinningMove(root=[1, 2, 3], n=3, x=1))