Skip to content

Commit ba32d1b

Browse files
YangFongYangFong
committed
feat: add solutions to lcci problem: No.04.02
No.04.02.Minimum Height Tree
1 parent 37fb98d commit ba32d1b

File tree

4 files changed

+204
-0
lines changed

4 files changed

+204
-0
lines changed

‎lcci/04.02.Minimum Height Tree/README.md

Lines changed: 71 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -142,6 +142,77 @@ func sortedArrayToBST(nums []int) *TreeNode {
142142
}
143143
```
144144

145+
### **TypeScript**
146+
147+
```ts
148+
/**
149+
* Definition for a binary tree node.
150+
* class TreeNode {
151+
* val: number
152+
* left: TreeNode | null
153+
* right: TreeNode | null
154+
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
155+
* this.val = (val===undefined ? 0 : val)
156+
* this.left = (left===undefined ? null : left)
157+
* this.right = (right===undefined ? null : right)
158+
* }
159+
* }
160+
*/
161+
162+
function sortedArrayToBST(nums: number[]): TreeNode | null {
163+
const dfs = (start: number, end: number): TreeNode | null => {
164+
if (start >= end) {
165+
return null;
166+
}
167+
const mid = Math.floor(start + (end - start) / 2);
168+
return new TreeNode(nums[mid], dfs(start, mid), dfs(mid + 1, end));
169+
};
170+
return dfs(0, nums.length);
171+
}
172+
```
173+
174+
### **Rust**
175+
176+
```rust
177+
// Definition for a binary tree node.
178+
// #[derive(Debug, PartialEq, Eq)]
179+
// pub struct TreeNode {
180+
// pub val: i32,
181+
// pub left: Option<Rc<RefCell<TreeNode>>>,
182+
// pub right: Option<Rc<RefCell<TreeNode>>>,
183+
// }
184+
//
185+
// impl TreeNode {
186+
// #[inline]
187+
// pub fn new(val: i32) -> Self {
188+
// TreeNode {
189+
// val,
190+
// left: None,
191+
// right: None
192+
// }
193+
// }
194+
// }
195+
use std::rc::Rc;
196+
use std::cell::RefCell;
197+
impl Solution {
198+
fn dfs(nums: &Vec<i32>, start: usize, end: usize) -> Option<Rc<RefCell<TreeNode>>> {
199+
if start >= end {
200+
return None;
201+
}
202+
let mid = start + (end - start) / 2;
203+
Some(Rc::new(RefCell::new(TreeNode {
204+
val: nums[mid],
205+
left: Self::dfs(nums, start, mid),
206+
right: Self::dfs(nums, mid + 1, end),
207+
})))
208+
}
209+
pub fn sorted_array_to_bst(nums: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
210+
let end = nums.len();
211+
Self::dfs(&nums, 0, end)
212+
}
213+
}
214+
```
215+
145216
### **...**
146217

147218
```

‎lcci/04.02.Minimum Height Tree/README_EN.md

Lines changed: 72 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -157,6 +157,78 @@ func sortedArrayToBST(nums []int) *TreeNode {
157157
}
158158
```
159159

160+
### **TypeScript**
161+
162+
```ts
163+
/**
164+
* Definition for a binary tree node.
165+
* class TreeNode {
166+
* val: number
167+
* left: TreeNode | null
168+
* right: TreeNode | null
169+
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
170+
* this.val = (val===undefined ? 0 : val)
171+
* this.left = (left===undefined ? null : left)
172+
* this.right = (right===undefined ? null : right)
173+
* }
174+
* }
175+
*/
176+
177+
function sortedArrayToBST(nums: number[]): TreeNode | null {
178+
const dfs = (start: number, end: number): TreeNode | null => {
179+
if (start >= end) {
180+
return null;
181+
}
182+
const mid = Math.floor(start + (end - start) / 2);
183+
return new TreeNode(nums[mid], dfs(start, mid), dfs(mid + 1, end));
184+
};
185+
return dfs(0, nums.length);
186+
}
187+
```
188+
189+
### **Rust**
190+
191+
```rust
192+
// Definition for a binary tree node.
193+
// #[derive(Debug, PartialEq, Eq)]
194+
// pub struct TreeNode {
195+
// pub val: i32,
196+
// pub left: Option<Rc<RefCell<TreeNode>>>,
197+
// pub right: Option<Rc<RefCell<TreeNode>>>,
198+
// }
199+
//
200+
// impl TreeNode {
201+
// #[inline]
202+
// pub fn new(val: i32) -> Self {
203+
// TreeNode {
204+
// val,
205+
// left: None,
206+
// right: None
207+
// }
208+
// }
209+
// }
210+
use std::rc::Rc;
211+
use std::cell::RefCell;
212+
impl Solution {
213+
fn dfs(nums: &Vec<i32>, start: usize, end: usize) -> Option<Rc<RefCell<TreeNode>>> {
214+
if start >= end {
215+
return None;
216+
}
217+
let mid = start + (end - start) / 2;
218+
Some(Rc::new(RefCell::new(TreeNode {
219+
val: nums[mid],
220+
left: Self::dfs(nums, start, mid),
221+
right: Self::dfs(nums, mid + 1, end),
222+
})))
223+
}
224+
pub fn sorted_array_to_bst(nums: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
225+
let end = nums.len();
226+
Self::dfs(&nums, 0, end)
227+
}
228+
}
229+
```
230+
231+
160232
### **...**
161233

162234
```

‎lcci/04.02.Minimum Height Tree/Solution.rs

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
// Definition for a binary tree node.
2+
// #[derive(Debug, PartialEq, Eq)]
3+
// pub struct TreeNode {
4+
// pub val: i32,
5+
// pub left: Option<Rc<RefCell<TreeNode>>>,
6+
// pub right: Option<Rc<RefCell<TreeNode>>>,
7+
// }
8+
//
9+
// impl TreeNode {
10+
// #[inline]
11+
// pub fn new(val: i32) -> Self {
12+
// TreeNode {
13+
// val,
14+
// left: None,
15+
// right: None
16+
// }
17+
// }
18+
// }
19+
use std::rc::Rc;
20+
use std::cell::RefCell;
21+
impl Solution {
22+
fn dfs(nums: &Vec<i32>, start: usize, end: usize) -> Option<Rc<RefCell<TreeNode>>> {
23+
if start >= end {
24+
return None;
25+
}
26+
let mid = start + (end - start) / 2;
27+
Some(Rc::new(RefCell::new(TreeNode {
28+
val: nums[mid],
29+
left: Self::dfs(nums, start, mid),
30+
right: Self::dfs(nums, mid + 1, end),
31+
})))
32+
}
33+
pub fn sorted_array_to_bst(nums: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
34+
let end = nums.len();
35+
Self::dfs(&nums, 0, end)
36+
}
37+
}

‎lcci/04.02.Minimum Height Tree/Solution.ts

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
/**
2+
* Definition for a binary tree node.
3+
* class TreeNode {
4+
* val: number
5+
* left: TreeNode | null
6+
* right: TreeNode | null
7+
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
8+
* this.val = (val===undefined ? 0 : val)
9+
* this.left = (left===undefined ? null : left)
10+
* this.right = (right===undefined ? null : right)
11+
* }
12+
* }
13+
*/
14+
15+
function sortedArrayToBST(nums: number[]): TreeNode | null {
16+
const dfs = (start: number, end: number): TreeNode | null => {
17+
if (start >= end) {
18+
return null;
19+
}
20+
const mid = Math.floor(start + (end - start) / 2);
21+
return new TreeNode(nums[mid], dfs(start, mid), dfs(mid + 1, end));
22+
};
23+
return dfs(0, nums.length);
24+
}

0 commit comments

Comments
 (0)