aboutsummaryrefslogtreecommitdiff
path: root/binary_tree_colouring_game.py
blob: b2b42f70640de8cb3bfebe023279d9b82cab7d41 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
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))