Skip to content

Commit 582773d

Browse files
YangFongYangFong
committed
feat: add solutions to lc problem: No.0669
No.0669.Trim a Binary Search Tree
1 parent 75edf4c commit 582773d

File tree

5 files changed

+330
-0
lines changed

5 files changed

+330
-0
lines changed

‎solution/0600-0699/0669.Trim a Binary Search Tree/README.md

Lines changed: 115 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -428,6 +428,121 @@ var trimBST = function (root, low, high) {
428428
};
429429
```
430430

431+
### **C**
432+
433+
```c
434+
/**
435+
* Definition for a binary tree node.
436+
* struct TreeNode {
437+
* int val;
438+
* struct TreeNode *left;
439+
* struct TreeNode *right;
440+
* };
441+
*/
442+
443+
444+
struct TreeNode *trimBST(struct TreeNode *root, int low, int high) {
445+
if (!root) {
446+
return root;
447+
}
448+
if (root->val < low) {
449+
return trimBST(root->right, low, high);
450+
}
451+
if (root->val > high) {
452+
return trimBST(root->left, low, high);
453+
}
454+
root->left = trimBST(root->left, low, high);
455+
root->right = trimBST(root->right, low, high);
456+
return root;
457+
}
458+
```
459+
460+
### **TypeScript**
461+
462+
```ts
463+
/**
464+
* Definition for a binary tree node.
465+
* class TreeNode {
466+
* val: number
467+
* left: TreeNode | null
468+
* right: TreeNode | null
469+
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
470+
* this.val = (val===undefined ? 0 : val)
471+
* this.left = (left===undefined ? null : left)
472+
* this.right = (right===undefined ? null : right)
473+
* }
474+
* }
475+
*/
476+
477+
function trimBST(
478+
root: TreeNode | null,
479+
low: number,
480+
high: number,
481+
): TreeNode | null {
482+
const dfs = (root: TreeNode | null) => {
483+
if (root == null) {
484+
return root;
485+
}
486+
const { val, left, right } = root;
487+
if (val < low || val > high) {
488+
return dfs(left) || dfs(right);
489+
}
490+
root.left = dfs(left);
491+
root.right = dfs(right);
492+
return root;
493+
};
494+
return dfs(root);
495+
}
496+
```
497+
498+
### **Rust**
499+
500+
```rust
501+
// Definition for a binary tree node.
502+
// #[derive(Debug, PartialEq, Eq)]
503+
// pub struct TreeNode {
504+
// pub val: i32,
505+
// pub left: Option<Rc<RefCell<TreeNode>>>,
506+
// pub right: Option<Rc<RefCell<TreeNode>>>,
507+
// }
508+
//
509+
// impl TreeNode {
510+
// #[inline]
511+
// pub fn new(val: i32) -> Self {
512+
// TreeNode {
513+
// val,
514+
// left: None,
515+
// right: None
516+
// }
517+
// }
518+
// }
519+
use std::rc::Rc;
520+
use std::cell::RefCell;
521+
impl Solution {
522+
pub fn trim_bst(
523+
mut root: Option<Rc<RefCell<TreeNode>>>,
524+
low: i32,
525+
high: i32,
526+
) -> Option<Rc<RefCell<TreeNode>>> {
527+
if root.is_none() {
528+
return root;
529+
}
530+
{
531+
let mut node = root.as_mut().unwrap().borrow_mut();
532+
if node.val < low {
533+
return Self::trim_bst(node.right.take(), low, high);
534+
}
535+
if node.val > high {
536+
return Self::trim_bst(node.left.take(), low, high);
537+
}
538+
node.left = Self::trim_bst(node.left.take(), low, high);
539+
node.right = Self::trim_bst(node.right.take(), low, high);
540+
}
541+
root
542+
}
543+
}
544+
```
545+
431546
### **...**
432547

433548
```

‎solution/0600-0699/0669.Trim a Binary Search Tree/README_EN.md

Lines changed: 115 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -390,6 +390,121 @@ var trimBST = function (root, low, high) {
390390
};
391391
```
392392

393+
### **C**
394+
395+
```c
396+
/**
397+
* Definition for a binary tree node.
398+
* struct TreeNode {
399+
* int val;
400+
* struct TreeNode *left;
401+
* struct TreeNode *right;
402+
* };
403+
*/
404+
405+
406+
struct TreeNode *trimBST(struct TreeNode *root, int low, int high) {
407+
if (!root) {
408+
return root;
409+
}
410+
if (root->val < low) {
411+
return trimBST(root->right, low, high);
412+
}
413+
if (root->val > high) {
414+
return trimBST(root->left, low, high);
415+
}
416+
root->left = trimBST(root->left, low, high);
417+
root->right = trimBST(root->right, low, high);
418+
return root;
419+
}
420+
```
421+
422+
### **TypeScript**
423+
424+
```ts
425+
/**
426+
* Definition for a binary tree node.
427+
* class TreeNode {
428+
* val: number
429+
* left: TreeNode | null
430+
* right: TreeNode | null
431+
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
432+
* this.val = (val===undefined ? 0 : val)
433+
* this.left = (left===undefined ? null : left)
434+
* this.right = (right===undefined ? null : right)
435+
* }
436+
* }
437+
*/
438+
439+
function trimBST(
440+
root: TreeNode | null,
441+
low: number,
442+
high: number,
443+
): TreeNode | null {
444+
const dfs = (root: TreeNode | null) => {
445+
if (root == null) {
446+
return root;
447+
}
448+
const { val, left, right } = root;
449+
if (val < low || val > high) {
450+
return dfs(left) || dfs(right);
451+
}
452+
root.left = dfs(left);
453+
root.right = dfs(right);
454+
return root;
455+
};
456+
return dfs(root);
457+
}
458+
```
459+
460+
### **Rust**
461+
462+
```rust
463+
// Definition for a binary tree node.
464+
// #[derive(Debug, PartialEq, Eq)]
465+
// pub struct TreeNode {
466+
// pub val: i32,
467+
// pub left: Option<Rc<RefCell<TreeNode>>>,
468+
// pub right: Option<Rc<RefCell<TreeNode>>>,
469+
// }
470+
//
471+
// impl TreeNode {
472+
// #[inline]
473+
// pub fn new(val: i32) -> Self {
474+
// TreeNode {
475+
// val,
476+
// left: None,
477+
// right: None
478+
// }
479+
// }
480+
// }
481+
use std::rc::Rc;
482+
use std::cell::RefCell;
483+
impl Solution {
484+
pub fn trim_bst(
485+
mut root: Option<Rc<RefCell<TreeNode>>>,
486+
low: i32,
487+
high: i32,
488+
) -> Option<Rc<RefCell<TreeNode>>> {
489+
if root.is_none() {
490+
return root;
491+
}
492+
{
493+
let mut node = root.as_mut().unwrap().borrow_mut();
494+
if node.val < low {
495+
return Self::trim_bst(node.right.take(), low, high);
496+
}
497+
if node.val > high {
498+
return Self::trim_bst(node.left.take(), low, high);
499+
}
500+
node.left = Self::trim_bst(node.left.take(), low, high);
501+
node.right = Self::trim_bst(node.right.take(), low, high);
502+
}
503+
root
504+
}
505+
}
506+
```
507+
393508
### **...**
394509

395510
```

‎solution/0600-0699/0669.Trim a Binary Search Tree/Solution.c

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+
* struct TreeNode {
4+
* int val;
5+
* struct TreeNode *left;
6+
* struct TreeNode *right;
7+
* };
8+
*/
9+
10+
11+
struct TreeNode *trimBST(struct TreeNode *root, int low, int high) {
12+
if (!root) {
13+
return root;
14+
}
15+
if (root->val < low) {
16+
return trimBST(root->right, low, high);
17+
}
18+
if (root->val > high) {
19+
return trimBST(root->left, low, high);
20+
}
21+
root->left = trimBST(root->left, low, high);
22+
root->right = trimBST(root->right, low, high);
23+
return root;
24+
}

‎solution/0600-0699/0669.Trim a Binary Search Tree/Solution.rs

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
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+
pub fn trim_bst(
23+
mut root: Option<Rc<RefCell<TreeNode>>>,
24+
low: i32,
25+
high: i32,
26+
) -> Option<Rc<RefCell<TreeNode>>> {
27+
if root.is_none() {
28+
return root;
29+
}
30+
{
31+
let mut node = root.as_mut().unwrap().borrow_mut();
32+
if node.val < low {
33+
return Self::trim_bst(node.right.take(), low, high);
34+
}
35+
if node.val > high {
36+
return Self::trim_bst(node.left.take(), low, high);
37+
}
38+
node.left = Self::trim_bst(node.left.take(), low, high);
39+
node.right = Self::trim_bst(node.right.take(), low, high);
40+
}
41+
root
42+
}
43+
}

‎solution/0600-0699/0669.Trim a Binary Search Tree/Solution.ts

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
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 trimBST(
16+
root: TreeNode | null,
17+
low: number,
18+
high: number,
19+
): TreeNode | null {
20+
const dfs = (root: TreeNode | null) => {
21+
if (root == null) {
22+
return root;
23+
}
24+
const { val, left, right } = root;
25+
if (val < low || val > high) {
26+
return dfs(left) || dfs(right);
27+
}
28+
root.left = dfs(left);
29+
root.right = dfs(right);
30+
return root;
31+
};
32+
return dfs(root);
33+
}

0 commit comments

Comments
 (0)