diff options
author | Jack Sangdahl <[email protected]> | 2024-11-18 10:31:36 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-11-18 10:31:36 -0700 |
commit | 4567a1b9e6047a644690115acd26fd2de32d3645 (patch) | |
tree | 281f6e75327112b75a1284fa8536cd4c92579ea7 | |
parent | f613f3233cef8aab33fe2f6ecbb65744b6321a85 (diff) | |
download | leetcode-4567a1b9e6047a644690115acd26fd2de32d3645.tar.gz leetcode-4567a1b9e6047a644690115acd26fd2de32d3645.zip |
1145. binary tree colouring game
-rw-r--r-- | binary_tree_colouring_game.c | 57 | ||||
-rw-r--r-- | binary_tree_colouring_game.py | 48 |
2 files changed, 105 insertions, 0 deletions
diff --git a/binary_tree_colouring_game.c b/binary_tree_colouring_game.c new file mode 100644 index 0000000..8e93a18 --- /dev/null +++ b/binary_tree_colouring_game.c @@ -0,0 +1,57 @@ +// 1145. Binary Tree Coloring Game +#include "leetcode.h" + +/* + * 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. + */ + +static int rc, lc; + +int get_rl(struct TreeNode *curr, int x, int found) { + if (!curr) + return 0; + int right, left; + if (curr->val == x) { + right = get_rl(curr->right, x, 1); + left = get_rl(curr->left, x, 1); + rc = right; + lc = left; + } + right = get_rl(curr->right, x, found); + left = get_rl(curr->left, x, found); + return found ? right + left + 1 : 0; +} + +bool btreeGameWinningMove(struct TreeNode *root, int n, int x) { + get_rl(root, x, 0); + int rem = n - (rc + lc + 1); + if (rem > rc + lc + 1 || rc > rem + lc + 1 || lc > rem + rc + 1) + return 1; + return 0; +} + +int main() { + struct TreeNode *r1 = treenode_create(1); + r1->left = treenode_create(2); + r1->right = treenode_create(3); + r1->left->left = treenode_create(4); + r1->left->right = treenode_create(5); + r1->left->left->left = treenode_create(8); + r1->left->left->right = treenode_create(9); + r1->right->left = treenode_create(6); + r1->right->right = treenode_create(7); + struct TreeNode *r2 = treenode_create(1); + r2->left = treenode_create(2); + r2->right = treenode_create(3); + printf("%d\n", btreeGameWinningMove(r1, 11, 3)); // expect: 1 + printf("%d\n", btreeGameWinningMove(r2, 3, 1)); // expect: 0 + treenode_free(r1), treenode_free(r2); +} 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)) |