diff options
Diffstat (limited to 'binary_tree_colouring_game.py')
-rw-r--r-- | binary_tree_colouring_game.py | 48 |
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)) |