64 lines
1.6 KiB
Rust
64 lines
1.6 KiB
Rust
// Definition for a binary tree node.
|
|
// #[derive(Debug, PartialEq, Eq)]
|
|
// pub struct TreeNode {
|
|
// pub val: i32,
|
|
// pub left: Option<Rc<RefCell<TreeNode>>>,
|
|
// pub right: Option<Rc<RefCell<TreeNode>>>,
|
|
// }
|
|
//
|
|
// impl TreeNode {
|
|
// #[inline]
|
|
// pub fn new(val: i32) -> Self {
|
|
// TreeNode {
|
|
// val,
|
|
// left: None,
|
|
// right: None
|
|
// }
|
|
// }
|
|
// }
|
|
|
|
use std::cell::RefCell;
|
|
use std::cmp;
|
|
use std::rc::Rc;
|
|
|
|
struct Result {
|
|
min: i32,
|
|
d: i32,
|
|
max: i32,
|
|
}
|
|
|
|
impl Solution {
|
|
fn find_min_diff(root: Option<Rc<RefCell<TreeNode>>>) -> Result {
|
|
match root {
|
|
None => Result {
|
|
min: i32::MAX,
|
|
d: i32::MAX,
|
|
max: i32::MIN,
|
|
},
|
|
Some(r) => {
|
|
let l_min = Solution::find_min_diff(r.borrow().left.clone());
|
|
let r_min = Solution::find_min_diff(r.borrow().right.clone());
|
|
|
|
let mut current_d = i32::MAX;
|
|
if l_min.max != i32::MIN {
|
|
current_d = (r.borrow().val - l_min.max).abs();
|
|
}
|
|
if r_min.min != i32::MAX {
|
|
current_d = cmp::min(current_d, (r_min.min - r.borrow().val).abs());
|
|
}
|
|
|
|
Result {
|
|
min: cmp::min(l_min.min, r.borrow().val),
|
|
d: cmp::min(cmp::min(l_min.d, r_min.d), current_d),
|
|
max: cmp::max(r.borrow().val, r_min.max),
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
pub fn get_minimum_difference(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
|
|
let r = Solution::find_min_diff(root);
|
|
|
|
r.d
|
|
}
|
|
}
|