diff options
author | Jack Sangdahl <[email protected]> | 2025-03-10 00:36:13 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-03-10 00:36:13 -0600 |
commit | 7c60dee83b436e8e8a667bf9f191beced8de4fc3 (patch) | |
tree | eb7a24ee2067f92245c57bb118e85a1baf15df50 /other/max_diff_node_ancestor.rs | |
parent | 5d7cdc215e4ba1ec4cbb24c084cccb5e5e641468 (diff) | |
download | leetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.tar.gz leetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.zip |
chore: move cpp and rust code to directory
Diffstat (limited to 'other/max_diff_node_ancestor.rs')
-rw-r--r-- | other/max_diff_node_ancestor.rs | 61 |
1 files changed, 61 insertions, 0 deletions
diff --git a/other/max_diff_node_ancestor.rs b/other/max_diff_node_ancestor.rs new file mode 100644 index 0000000..671bd27 --- /dev/null +++ b/other/max_diff_node_ancestor.rs @@ -0,0 +1,61 @@ +use std::cmp; +use std::rc::Rc; +use std::cell::RefCell; + +#[derive(Debug, PartialEq, Eq)] +pub struct TreeNode { + pub val: i32, + pub left: Option<Rc<RefCell<TreeNode>>>, + pub right: Option<Rc<RefCell<TreeNode>>> +} + +struct MinMax { + min: i32, + max: i32, + ans: i32 +} + +impl TreeNode { + #[inline] + pub fn new(val: i32) -> Self { + TreeNode { + val, + left: None, + right: None + } + } +} + +impl Solution { + fn minMax(node_ref: Rc<RefCell<TreeNode>>) -> MinMax { + let node = node_ref.borrow(); + let mut a = MinMax { + min: node.val, + max: node.val, + ans: 0 + }; + if node.left.is_none() && node.right.is_none() { + a + } else { + let children = vec![&node.left, &node.right]; + for child_option in children.iter() { + if let Some(child) = child_option { + let c = Self::minMax(Rc::clone(&child)); + a.ans = cmp::max(a.ans, c.ans); + a.ans = cmp::max(a.ans, (node.val - c.min).abs()); + a.ans = cmp::max(a.ans, (node.val - c.max).abs()); + a.min = cmp::min(a.min, c.min); + a.max = cmp::max(a.max, c.max); + } + } + a + } + } + pub fn max_ancestor_diff(root: Option<Rc<RefCell<TreeNode>>>) -> i32 { + if let Some(node_ref) = root { + Self::minMax(Rc::clone(&node_ref)).ans + } else { + panic!("bad input"); + } + } +} |