leetcode

commit 739f042f2cd9dc7ac136d82c5698eaaefe63d5ba
parent 0c6c79eaf07384f8c1aa1c571e240476e5cc0d19
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Mon, 22 Apr 2024 15:58:55 +0200

1 Random Problem

Diffstat:
A
Problems/1145.cpp
 | 
16
++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 17 insertions(+), 0 deletions(-)
diff --git a/Problems/1145.cpp b/Problems/1145.cpp
@@ -0,0 +1,16 @@
+class Solution {
+    mutable int left, right, val;
+
+    int count(const TreeNode *node) const {
+        if (!node) return 0;
+        int l = count(node->left), r = count(node->right);
+        if (node->val == val) left = l, right = r;
+        return l + r + 1;
+    }
+
+  public:
+    bool btreeGameWinningMove(const TreeNode *root, int n, int x) const {
+        val = x, n = count(root);
+        return max(max(left, right), n - left - right - 1) > n / 2;
+    }
+};
diff --git a/README.md b/README.md
@@ -659,6 +659,7 @@ for solving problems.
 |  1140  |   Medium   | [Stone Game II](Problems/1140.cpp)                                                                 |
 |  1141  |    Easy    | [User Activity for the Past 30 Days I](Problems/1141.cpp)                                          |
 |  1143  |   Medium   | [Longest Common Subsequence](Problems/1143.cpp)                                                    |
+|  1145  |   Medium   | [Binary Tree Coloring Game](Problems/1145.cpp)                                                     |
 |  1146  |   Medium   | [Snapshot Array](Problems/1146.cpp)                                                                |
 |  1148  |    Easy    | [Article Views I](Problems/1148.cpp)                                                               |
 |  1155  |   Medium   | [Number of Dice Rolls With Target Sum](Problems/1155.cpp)                                          |