8000 idk · jhideki/rust_leetcode@7702d47 · GitHub
[go: up one dir, main page]
Skip to content

Commit 7702d47

Browse files
jhidekijhideki
committed
idk
1 parent 6d52073 commit 7702d47

File tree

7 files changed

+183
-2
lines changed

7 files changed

+183
-2
lines changed

‎src/balanced_tree.rs

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
use crate::TreeNode;
2+
use std::cell::RefCell;
3+
use std::rc::Rc;
4+
pub struct Solution {}
5+
6+
impl Solution {
7+
pub fn is_balanced(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
8+
fn height(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
9+
if let Some(node) = root {
10+
let node = node.borrow();
11+
let lh = height(node.left.clone());
12+
if lh == -1 {
13+
return -1;
14+
}
15+
let rh = height(node.right.clone());
16+
if rh == -1 {
17+
return -1;
18+
}
19+
if (lh - rh).abs() > 1 {
20+
return -1;
21+
}
22+
return std::cmp::max(lh, rh) + 1;
23+
}
24+
0
25+
}
26+
if height(root) != -1 {
27+
return true;
28+
}
29+
false
30+
}
31+
}

‎src/common_ancestor.rs

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
use crate::TreeNode;
2+
use std::cell::RefCell;
3+
use std::rc::Rc;
4+
pub struct Solution {}
5+
impl Solution {
6+
pub fn lowest_common_ancestor(
7+
root: Option<Rc<RefCell<TreeNode>>>,
8+
p: Option<Rc<RefCell<TreeNode>>>,
9+
q: Option<Rc<RefCell<TreeNode>>>,
10+
) -> Option<Rc<RefCell<TreeNode>>> {
11+
let mut cur = root;
12+
13+
let q = q.unwrap();
14+
let q = q.borrow();
15+
16+
let p = p.unwrap();
17+
let p = p.borrow();
18+
while let Some(node) = cur {
19+
let val = node.borrow().val;
20+
if p.val < val && q.val < val {
21+
cur = node.borrow().left.clone();
22+
} else if p.val > val && p.val < val {
23+
cur = node.borrow().right.clone();
24+
} else {
25+
return Some(node);
26+
}
27+
}
28+
None
29+
}
30+
}

‎src/diameter_tree.rs

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
use crate::TreeNode;
2+
use std::cell::RefCell;
3+
use std::rc::Rc;
4+
pub struct Solution {}
5+
impl Solution {
6+
pub fn diameter_of_binary_tree(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
7+
let mut res = 0;
8+
9+
fn dfs(root: Option<Rc<RefCell<TreeNode>>>, res: &mut i32) -> i32 {
10+
if let Some(node) = root {
11+
let node = node.borrow();
12+
let left = dfs(node.left.clone(), res);
13+
let right = dfs(node.right.clone(), res);
14+
*res = std::cmp::max(*res, 2 + left + right);
15+
return 1 + std::cmp::max(left, right);
16+
}
17+
-1
18+
}
19+
dfs(root, &mut res);
20+
res
21+
}
22+
}

‎src/level_order.rs

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
use crate::TreeNode;
2+
use ::std::collections::VecDeque;
3+
use std::cell::RefCell;
4+
use std::rc::Rc;
5+
pub struct Solution {}
6+
impl Solution {
7+
pub fn level_order(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<i32>> {
8+
let mut queue = VecDeque::new();
9+
let mut res: Vec<Vec<i32>> = Vec::new();
10+
queue.push_back(root);
11+
while !queue.is_empty() {
12+
let len = queue.len();
13+
let mut level: Vec<i32> = Vec::new();
14+
for _i in 0..len {
15+
if let Some(node) = queue.pop_front().unwrap() {
16+
let n = node.borrow();
17+
level.push(n.val.clone());
18+
queue.push_back(n.left.clone());
19+
queue.push_back(n.right.clone());
20+
}
21+
}
22+
if level.is
23+
res.push(level)
24+
}
25+
res
26+
}
27+
}

‎src/main.rs

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,5 @@
1-
mod max_depth;
2-
use max_depth::Solution;
1+
mod level_order;
2+
use level_order::Solution;
33
use std::cell::RefCell;
44
use std::rc::Rc;
55
#[derive(Debug, PartialEq, Eq)]

‎src/same_tree.rs

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
use crate::TreeNode;
2+
use std::cell::RefCell;
3+
use std::rc::Rc;
4+
pub struct Solution {}
5+
impl Solution {
6+
pub fn is_same_tree(
7+
p: Option<Rc<RefCell<TreeNode>>>,
8+
q: Option<Rc<RefCell<TreeNode>>>,
9+
) -> bool {
10+
if p.is_none() && q.is_none() {
11+
return true;
12+
}
13+
if let (Some(node), Some(node2)) = (p, q) {
14+
let node1 = node.borrow();
15+
let node2 = node2.borrow();
16+
17+
if node1.val != node2.val {
18+
return false;
19+
}
20+
21+
return Self::is_same_tree(node1.left.clone(), node2.left.clone())
22+
&& Self::is_same_tree(node1.right.clone(), node2.right.clone());
23+
}
24+
false
25+
}
26+
}

‎src/subtree_of_another.rs

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
use crate::TreeNode;
2+
use std::cell::RefCell;
3+
use std::rc::Rc;
4+
pub struct Solution {}
5+
impl Solution {
6+
pub fn is_subtree(
7+
root: Option<Rc<RefCell<TreeNode>>>,
8+
sub_root: Option<Rc<RefCell<TreeNode>>>,
9+
) -> bool {
10+
if sub_root.is_none() {
11+
return true;
12+
}
13+
if root.is_none() {
14+
return false;
15+
}
16+
if Self::is_same_tree(root.clone(), sub_root) {
17+
return true;
18+
}
19+
20+
let node = root.unwrap().borrow();
21+
Self::is_subtree(node.right.clone(), sub_root.clone())
22+
|| Self::is_subtree(node.left.clone(), sub_root.clone())
23+
}
 A851
24+
25+
pub fn is_same_tree(
26+
p: Option<Rc<RefCell<TreeNode>>>,
27+
q: Option<Rc<RefCell<TreeNode>>>,
28+
) -> bool {
29+
if p.is_none() && q.is_none() {
30+
return true;
31+
}
32+
33+
if let (Some(n1), Some(n2)) = (p, q) {
34+
let node1 = n1.borrow();
35+
let node2 = n2.borrow();
36+
37+
if node1.val != node2.val {
38+
return false;
39+
}
40+
return Self::is_same_tree(node1.left.clone(), node2.left.clone())
41+
&& Self::is_same_tree(node1.right.clone(), node2.left.clone());
42+
}
43+
false
44+
}
45+
}

0 commit comments

Comments
 (0)
0