aboutsummaryrefslogtreecommitdiff
path: root/max_diff_node_ancestor.rs
diff options
context:
space:
mode:
authorjack <[email protected]>2024-06-14 13:13:15 -0600
committerjack <[email protected]>2024-06-14 13:13:15 -0600
commitd343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch)
tree96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /max_diff_node_ancestor.rs
downloadleetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz
leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip
initial
Diffstat (limited to 'max_diff_node_ancestor.rs')
-rw-r--r--max_diff_node_ancestor.rs61
1 files changed, 61 insertions, 0 deletions
diff --git a/max_diff_node_ancestor.rs b/max_diff_node_ancestor.rs
new file mode 100644
index 0000000..671bd27
--- /dev/null
+++ b/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");
+ }
+ }
+}