Skip to content

Commit da55c3a

Browse files
yanglbmeyanglbme
committed
feat: add solutions to lc problem: No.0270. Closest Binary Search Tree Value
1 parent d2d1e39 commit da55c3a

File tree

7 files changed

+455
-2
lines changed

7 files changed

+455
-2
lines changed

‎solution/0200-0299/0270.Closest Binary Search Tree Value/README.md

Lines changed: 157 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -33,22 +33,178 @@
3333

3434
<!-- 这里可写通用的实现逻辑 -->
3535

36+
二分查找。
37+
3638
<!-- tabs:start -->
3739

3840
### **Python3**
3941

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

4244
```python
43-
45+
# Definition for a binary tree node.
46+
# class TreeNode:
47+
# def __init__(self, val=0, left=None, right=None):
48+
# self.val = val
49+
# self.left = left
50+
# self.right = right
51+
class Solution:
52+
def closestValue(self, root: TreeNode, target: float) -> int:
53+
res, min_diff = root.val, float('inf')
54+
while root:
55+
val = abs(root.val - target)
56+
if min_diff > val:
57+
min_diff = val
58+
res = root.val
59+
if root.val > target:
60+
root = root.left
61+
else:
62+
root = root.right
63+
return res
4464
```
4565

4666
### **Java**
4767

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

5070
```java
71+
/**
72+
* Definition for a binary tree node.
73+
* public class TreeNode {
74+
* int val;
75+
* TreeNode left;
76+
* TreeNode right;
77+
* TreeNode() {}
78+
* TreeNode(int val) { this.val = val; }
79+
* TreeNode(int val, TreeNode left, TreeNode right) {
80+
* this.val = val;
81+
* this.left = left;
82+
* this.right = right;
83+
* }
84+
* }
85+
*/
86+
class Solution {
87+
public int closestValue(TreeNode root, double target) {
88+
int res = root.val;
89+
double minDiff = Double.MAX_VALUE;
90+
while (root != null) {
91+
double val = Math.abs(root.val - target);
92+
if (minDiff > val) {
93+
minDiff = val;
94+
res = root.val;
95+
}
96+
if (root.val > target) {
97+
root = root.left;
98+
} else {
99+
root = root.right;
100+
}
101+
}
102+
return res;
103+
}
104+
}
105+
```
106+
107+
### **JavaScript**
108+
109+
```js
110+
/**
111+
* Definition for a binary tree node.
112+
* function TreeNode(val, left, right) {
113+
* this.val = (val===undefined ? 0 : val)
114+
* this.left = (left===undefined ? null : left)
115+
* this.right = (right===undefined ? null : right)
116+
* }
117+
*/
118+
/**
119+
* @param {TreeNode} root
120+
* @param {number} target
121+
* @return {number}
122+
*/
123+
var closestValue = function(root, target) {
124+
let res = root.val;
125+
let minDiff = Math.abs(root.val - target);
126+
while (root) {
127+
const val = Math.abs(root.val - target);
128+
if (minDiff > val) {
129+
minDiff = val;
130+
res = root.val;
131+
}
132+
if (root.val > target) {
133+
root = root.left;
134+
} else {
135+
root = root.right;
136+
}
137+
}
138+
return res;
139+
};
140+
```
141+
142+
### **C++**
143+
144+
```cpp
145+
/**
146+
* Definition for a binary tree node.
147+
* struct TreeNode {
148+
* int val;
149+
* TreeNode *left;
150+
* TreeNode *right;
151+
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
152+
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
153+
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
154+
* };
155+
*/
156+
class Solution {
157+
public:
158+
int closestValue(TreeNode* root, double target) {
159+
int res = root->val;
160+
double minDiff = abs(root->val - target);
161+
while (root != nullptr) {
162+
double val = abs(root->val - target);
163+
if (minDiff > val) {
164+
minDiff = val;
165+
res = root->val;
166+
}
167+
if (root->val > target) {
168+
root = root->left;
169+
} else {
170+
root = root->right;
171+
}
172+
}
173+
return res;
174+
}
175+
};
176+
```
51177
178+
### **Go**
179+
180+
```go
181+
import "math"
182+
183+
/**
184+
* Definition for a binary tree node.
185+
* type TreeNode struct {
186+
* Val int
187+
* Left *TreeNode
188+
* Right *TreeNode
189+
* }
190+
*/
191+
func closestValue(root *TreeNode, target float64) int {
192+
res := root.Val
193+
minDiff := math.Abs(float64(root.Val) - float64(target))
194+
for root != nil {
195+
val := math.Abs(float64(root.Val) - float64(target))
196+
if minDiff > val {
197+
minDiff = val
198+
res = root.Val
199+
}
200+
if float64(root.Val) > target {
201+
root = root.Left
202+
} else {
203+
root = root.Right
204+
}
205+
}
206+
return res
207+
}
52208
```
53209

54210
### **...**

‎solution/0200-0299/0270.Closest Binary Search Tree Value/README_EN.md

Lines changed: 157 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -33,18 +33,174 @@
3333

3434
## Solutions
3535

36+
Binary search.
37+
3638
<!-- tabs:start -->
3739

3840
### **Python3**
3941

4042
```python
41-
43+
# Definition for a binary tree node.
44+
# class TreeNode:
45+
# def __init__(self, val=0, left=None, right=None):
46+
# self.val = val
47+
# self.left = left
48+
# self.right = right
49+
class Solution:
50+
def closestValue(self, root: TreeNode, target: float) -> int:
51+
res, min_diff = root.val, float('inf')
52+
while root:
53+
val = abs(root.val - target)
54+
if min_diff > val:
55+
min_diff = val
56+
res = root.val
57+
if root.val > target:
58+
root = root.left
59+
else:
60+
root = root.right
61+
return res
4262
```
4363

4464
### **Java**
4565

4666
```java
67+
/**
68+
* Definition for a binary tree node.
69+
* public class TreeNode {
70+
* int val;
71+
* TreeNode left;
72+
* TreeNode right;
73+
* TreeNode() {}
74+
* TreeNode(int val) { this.val = val; }
75+
* TreeNode(int val, TreeNode left, TreeNode right) {
76+
* this.val = val;
77+
* this.left = left;
78+
* this.right = right;
79+
* }
80+
* }
81+
*/
82+
class Solution {
83+
public int closestValue(TreeNode root, double target) {
84+
int res = root.val;
85+
double minDiff = Double.MAX_VALUE;
86+
while (root != null) {
87+
double val = Math.abs(root.val - target);
88+
if (minDiff > val) {
89+
minDiff = val;
90+
res = root.val;
91+
}
92+
if (root.val > target) {
93+
root = root.left;
94+
} else {
95+
root = root.right;
96+
}
97+
}
98+
return res;
99+
}
100+
}
101+
```
102+
103+
### **JavaScript**
104+
105+
```js
106+
/**
107+
* Definition for a binary tree node.
108+
* function TreeNode(val, left, right) {
109+
* this.val = (val===undefined ? 0 : val)
110+
* this.left = (left===undefined ? null : left)
111+
* this.right = (right===undefined ? null : right)
112+
* }
113+
*/
114+
/**
115+
* @param {TreeNode} root
116+
* @param {number} target
117+
* @return {number}
118+
*/
119+
var closestValue = function(root, target) {
120+
let res = root.val;
121+
let minDiff = Math.abs(root.val - target);
122+
while (root) {
123+
const val = Math.abs(root.val - target);
124+
if (minDiff > val) {
125+
minDiff = val;
126+
res = root.val;
127+
}
128+
if (root.val > target) {
129+
root = root.left;
130+
} else {
131+
root = root.right;
132+
}
133+
}
134+
return res;
135+
};
136+
```
137+
138+
### **C++**
139+
140+
```cpp
141+
/**
142+
* Definition for a binary tree node.
143+
* struct TreeNode {
144+
* int val;
145+
* TreeNode *left;
146+
* TreeNode *right;
147+
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
148+
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
149+
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
150+
* };
151+
*/
152+
class Solution {
153+
public:
154+
int closestValue(TreeNode* root, double target) {
155+
int res = root->val;
156+
double minDiff = abs(root->val - target);
157+
while (root != nullptr) {
158+
double val = abs(root->val - target);
159+
if (minDiff > val) {
160+
minDiff = val;
161+
res = root->val;
162+
}
163+
if (root->val > target) {
164+
root = root->left;
165+
} else {
166+
root = root->right;
167+
}
168+
}
169+
return res;
170+
}
171+
};
172+
```
47173
174+
### **Go**
175+
176+
```go
177+
import "math"
178+
179+
/**
180+
* Definition for a binary tree node.
181+
* type TreeNode struct {
182+
* Val int
183+
* Left *TreeNode
184+
* Right *TreeNode
185+
* }
186+
*/
187+
func closestValue(root *TreeNode, target float64) int {
188+
res := root.Val
189+
minDiff := math.Abs(float64(root.Val) - float64(target))
190+
for root != nil {
191+
val := math.Abs(float64(root.Val) - float64(target))
192+
if minDiff > val {
193+
minDiff = val
194+
res = root.Val
195+
}
196+
if float64(root.Val) > target {
197+
root = root.Left
198+
} else {
199+
root = root.Right
200+
}
201+
}
202+
return res
203+
}
48204
```
49205

50206
### **...**

‎solution/0200-0299/0270.Closest Binary Search Tree Value/Solution.cpp

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
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+
int closestValue(TreeNode* root, double target) {
15+
int res = root->val;
16+
double minDiff = abs(root->val - target);
17+
while (root != nullptr) {
18+
double val = abs(root->val - target);
19+
if (minDiff > val) {
20+
minDiff = val;
21+
res = root->val;
22+
}
23+
if (root->val > target) {
24+
root = root->left;
25+
} else {
26+
root = root->right;
27+
}
28+
}
29+
return res;
30+
}
31+
};

0 commit comments

Comments
 (0)