Given the root of a binary tree, find the maximum value V for which there exist different nodes A and B where V = |A.val - B.val| and A is an ancestor of B.
A node A is an ancestor of B if either: any child of A is equal to B, or any child of A is an ancestor of B.
Example 1:
Input: root = [8,3,10,1,6,null,14,null,null,4,7,13] Output: 7 Explanation: We have various ancestor-node differences, some of which are given below : |8 - 3| = 5 |3 - 7| = 4 |8 - 1| = 7 |10 - 13| = 3 Among all possible differences, the maximum value of 7 is obtained by |8 - 1| = 7.
Example 2:
Input: root = [1,null,2,null,0,3] Output: 3
Constraints:
- The number of nodes in the tree is in the range
[2, 5000]. 0 <= Node.val <= 105
struct Solution;
use rustgym_util::*;
trait Preorder {
fn preorder(&self, parent: Option<(i32, i32)>, abs: &mut i32);
}
impl Preorder for TreeLink {
fn preorder(&self, mut parent: Option<(i32, i32)>, abs: &mut i32) {
if let Some(node) = self {
let val = node.borrow().val;
let left = &node.borrow().left;
let right = &node.borrow().right;
parent = if let Some((min, max)) = parent {
*abs = (*abs).max((min - val).abs().max((max - val).abs()));
Some((min.min(val), max.max(val)))
} else {
Some((val, val))
};
left.preorder(parent, abs);
right.preorder(parent, abs);
}
}
}
impl Solution {
fn max_ancestor_diff(root: TreeLink) -> i32 {
let mut res = 0;
root.preorder(None, &mut res);
res
}
}
#[test]
fn test() {
let root = tree!(
8,
tree!(3, tree!(1), tree!(6, tree!(4), tree!(7))),
tree!(10, None, tree!(14, tree!(13), None))
);
let res = 7;
assert_eq!(Solution::max_ancestor_diff(root), res);
}