1026. Maximum Difference Between Node and Ancestor

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

Rust Solution

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);
}