aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-11-18 10:31:36 -0700
committerJack Sangdahl <[email protected]>2024-11-18 10:31:36 -0700
commit4567a1b9e6047a644690115acd26fd2de32d3645 (patch)
tree281f6e75327112b75a1284fa8536cd4c92579ea7
parentf613f3233cef8aab33fe2f6ecbb65744b6321a85 (diff)
downloadleetcode-4567a1b9e6047a644690115acd26fd2de32d3645.tar.gz
leetcode-4567a1b9e6047a644690115acd26fd2de32d3645.zip
1145. binary tree colouring game
-rw-r--r--binary_tree_colouring_game.c57
-rw-r--r--binary_tree_colouring_game.py48
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))