Skip to content

Commit 6a0ab08

Browse files
yanglbmeyanglbme
committed
feat: add solutions to lc problem: No.1145
No.1145.Binary Tree Coloring Game
1 parent 84a2672 commit 6a0ab08

File tree

6 files changed

+434
-2
lines changed

6 files changed

+434
-2
lines changed

‎solution/1100-1199/1145.Binary Tree Coloring Game/README.md

Lines changed: 153 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -55,22 +55,174 @@
5555

5656
<!-- 这里可写通用的实现逻辑 -->
5757

58+
**方法一：DFS**
59+
60+
先通过 $DFS$，找到 $x$ 所在的节点，我们记为 $node$。然后统计 $node$ 的左子树、右子树、父节点方向上的节点个数。如果这三个方向上有任何一个节点个数超过了节点总数的一半，则存在一个必胜策略。
61+
62+
这里 $node$ 父节点方向上的节点个数，可以由节点总数 $n$ 减去 $node$ 及其 $node$ 的左右子树节点数之和得到。
63+
64+
时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是节点总数。
65+
5866
<!-- tabs:start -->
5967

6068
### **Python3**
6169

6270
<!-- 这里可写当前语言的特殊实现逻辑 -->
6371

6472
```python
65-
73+
# Definition for a binary tree node.
74+
# class TreeNode:
75+
# def __init__(self, val=0, left=None, right=None):
76+
# self.val = val
77+
# self.left = left
78+
# self.right = right
79+
class Solution:
80+
def btreeGameWinningMove(self, root: Optional[TreeNode], n: int, x: int) -> bool:
81+
def dfs(root):
82+
if root is None or root.val == x:
83+
return root
84+
return dfs(root.left) or dfs(root.right)
85+
86+
def count(root):
87+
if root is None:
88+
return 0
89+
return 1 + count(root.left) + count(root.right)
90+
91+
node = dfs(root)
92+
l, r = count(node.left), count(node.right)
93+
t = n - l - r - 1
94+
m = max(l, r, t)
95+
return m > n - m
6696
```
6797

6898
### **Java**
6999

70100
<!-- 这里可写当前语言的特殊实现逻辑 -->
71101

72102
```java
103+
/**
104+
* Definition for a binary tree node.
105+
* public class TreeNode {
106+
* int val;
107+
* TreeNode left;
108+
* TreeNode right;
109+
* TreeNode() {}
110+
* TreeNode(int val) { this.val = val; }
111+
* TreeNode(int val, TreeNode left, TreeNode right) {
112+
* this.val = val;
113+
* this.left = left;
114+
* this.right = right;
115+
* }
116+
* }
117+
*/
118+
class Solution {
119+
public boolean btreeGameWinningMove(TreeNode root, int n, int x) {
120+
TreeNode node = dfs(root, x);
121+
int l = count(node.left);
122+
int r = count(node.right);
123+
int m = Math.max(Math.max(l, r), n - l - r - 1);
124+
return m > n - m;
125+
}
126+
127+
private int count(TreeNode node) {
128+
if (node == null) {
129+
return 0;
130+
}
131+
return 1 + count(node.left) + count(node.right);
132+
}
133+
134+
private TreeNode dfs(TreeNode root, int x) {
135+
if (root == null || root.val == x) {
136+
return root;
137+
}
138+
TreeNode l = dfs(root.left, x);
139+
if (l != null) {
140+
return l;
141+
}
142+
return dfs(root.right, x);
143+
}
144+
}
145+
```
146+
147+
### **C++**
148+
149+
```cpp
150+
/**
151+
* Definition for a binary tree node.
152+
* struct TreeNode {
153+
* int val;
154+
* TreeNode *left;
155+
* TreeNode *right;
156+
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
157+
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
158+
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
159+
* };
160+
*/
161+
class Solution {
162+
public:
163+
bool btreeGameWinningMove(TreeNode* root, int n, int x) {
164+
TreeNode* node = dfs(root, x);
165+
int l = count(node->left);
166+
int r = count(node->right);
167+
int m = max(max(l, r), n - l - r - 1);
168+
return m > n - m;
169+
}
170+
171+
int count(TreeNode* root) {
172+
if (!root) return 0;
173+
return 1 + count(root->left) + count(root->right);
174+
}
175+
176+
TreeNode* dfs(TreeNode* root, int x) {
177+
if (!root || root->val == x) return root;
178+
auto l = dfs(root->left, x);
179+
return l ? l : dfs(root->right, x);
180+
}
181+
};
182+
```
73183
184+
### **Go**
185+
186+
```go
187+
/**
188+
* Definition for a binary tree node.
189+
* type TreeNode struct {
190+
* Val int
191+
* Left *TreeNode
192+
* Right *TreeNode
193+
* }
194+
*/
195+
func btreeGameWinningMove(root *TreeNode, n int, x int) bool {
196+
var dfs func(*TreeNode) *TreeNode
197+
dfs = func(root *TreeNode) *TreeNode {
198+
if root == nil || root.Val == x {
199+
return root
200+
}
201+
l := dfs(root.Left)
202+
if l != nil {
203+
return l
204+
}
205+
return dfs(root.Right)
206+
}
207+
var count func(*TreeNode) int
208+
count = func(root *TreeNode) int {
209+
if root == nil {
210+
return 0
211+
}
212+
return 1 + count(root.Left) + count(root.Right)
213+
}
214+
node := dfs(root)
215+
l, r := count(node.Left), count(node.Right)
216+
m := max(max(l, r), n-l-r-1)
217+
return m > n-m
218+
}
219+
220+
func max(a, b int) int {
221+
if a > b {
222+
return a
223+
}
224+
return b
225+
}
74226
```
75227

76228
### **...**

‎solution/1100-1199/1145.Binary Tree Coloring Game/README_EN.md

Lines changed: 145 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -48,13 +48,157 @@
4848
### **Python3**
4949

5050
```python
51-
51+
# Definition for a binary tree node.
52+
# class TreeNode:
53+
# def __init__(self, val=0, left=None, right=None):
54+
# self.val = val
55+
# self.left = left
56+
# self.right = right
57+
class Solution:
58+
def btreeGameWinningMove(self, root: Optional[TreeNode], n: int, x: int) -> bool:
59+
def dfs(root):
60+
if root is None or root.val == x:
61+
return root
62+
return dfs(root.left) or dfs(root.right)
63+
64+
def count(root):
65+
if root is None:
66+
return 0
67+
return 1 + count(root.left) + count(root.right)
68+
69+
node = dfs(root)
70+
l, r = count(node.left), count(node.right)
71+
t = n - l - r - 1
72+
m = max(l, r, t)
73+
return m > n - m
5274
```
5375

5476
### **Java**
5577

5678
```java
79+
/**
80+
* Definition for a binary tree node.
81+
* public class TreeNode {
82+
* int val;
83+
* TreeNode left;
84+
* TreeNode right;
85+
* TreeNode() {}
86+
* TreeNode(int val) { this.val = val; }
87+
* TreeNode(int val, TreeNode left, TreeNode right) {
88+
* this.val = val;
89+
* this.left = left;
90+
* this.right = right;
91+
* }
92+
* }
93+
*/
94+
class Solution {
95+
public boolean btreeGameWinningMove(TreeNode root, int n, int x) {
96+
TreeNode node = dfs(root, x);
97+
int l = count(node.left);
98+
int r = count(node.right);
99+
int m = Math.max(Math.max(l, r), n - l - r - 1);
100+
return m > n - m;
101+
}
102+
103+
private int count(TreeNode node) {
104+
if (node == null) {
105+
return 0;
106+
}
107+
return 1 + count(node.left) + count(node.right);
108+
}
109+
110+
private TreeNode dfs(TreeNode root, int x) {
111+
if (root == null || root.val == x) {
112+
return root;
113+
}
114+
TreeNode l = dfs(root.left, x);
115+
if (l != null) {
116+
return l;
117+
}
118+
return dfs(root.right, x);
119+
}
120+
}
121+
```
122+
123+
### **C++**
124+
125+
```cpp
126+
/**
127+
* Definition for a binary tree node.
128+
* struct TreeNode {
129+
* int val;
130+
* TreeNode *left;
131+
* TreeNode *right;
132+
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
133+
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
134+
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
135+
* };
136+
*/
137+
class Solution {
138+
public:
139+
bool btreeGameWinningMove(TreeNode* root, int n, int x) {
140+
TreeNode* node = dfs(root, x);
141+
int l = count(node->left);
142+
int r = count(node->right);
143+
int m = max(max(l, r), n - l - r - 1);
144+
return m > n - m;
145+
}
146+
147+
int count(TreeNode* root) {
148+
if (!root) return 0;
149+
return 1 + count(root->left) + count(root->right);
150+
}
151+
152+
TreeNode* dfs(TreeNode* root, int x) {
153+
if (!root || root->val == x) return root;
154+
auto l = dfs(root->left, x);
155+
return l ? l : dfs(root->right, x);
156+
}
157+
};
158+
```
57159
160+
### **Go**
161+
162+
```go
163+
/**
164+
* Definition for a binary tree node.
165+
* type TreeNode struct {
166+
* Val int
167+
* Left *TreeNode
168+
* Right *TreeNode
169+
* }
170+
*/
171+
func btreeGameWinningMove(root *TreeNode, n int, x int) bool {
172+
var dfs func(*TreeNode) *TreeNode
173+
dfs = func(root *TreeNode) *TreeNode {
174+
if root == nil || root.Val == x {
175+
return root
176+
}
177+
l := dfs(root.Left)
178+
if l != nil {
179+
return l
180+
}
181+
return dfs(root.Right)
182+
}
183+
var count func(*TreeNode) int
184+
count = func(root *TreeNode) int {
185+
if root == nil {
186+
return 0
187+
}
188+
return 1 + count(root.Left) + count(root.Right)
189+
}
190+
node := dfs(root)
191+
l, r := count(node.Left), count(node.Right)
192+
m := max(max(l, r), n-l-r-1)
193+
return m > n-m
194+
}
195+
196+
func max(a, b int) int {
197+
if a > b {
198+
return a
199+
}
200+
return b
201+
}
58202
```
59203

60204
### **...**

‎solution/1100-1199/1145.Binary Tree Coloring Game/Solution.cpp

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
/**
2+
* Definition for a binary tree node.
3+
* struct TreeNode {
4+
* int val;
5+
* TreeNode *left;
6+
* TreeNode *right;
7+
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
8+
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9+
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10+
* };
11+
*/
12+
class Solution {
13+
public:
14+
bool btreeGameWinningMove(TreeNode* root, int n, int x) {
15+
TreeNode* node = dfs(root, x);
16+
int l = count(node->left);
17+
int r = count(node->right);
18+
int m = max(max(l, r), n - l - r - 1);
19+
return m > n - m;
20+
}
21+
22+
int count(TreeNode* root) {
23+
if (!root) return 0;
24+
return 1 + count(root->left) + count(root->right);
25+
}
26+
27+
TreeNode* dfs(TreeNode* root, int x) {
28+
if (!root || root->val == x) return root;
29+
auto l = dfs(root->left, x);
30+
return l ? l : dfs(root->right, x);
31+
}
32+
};

0 commit comments

Comments
 (0)