1026. Maximum Difference Between Node and Ancestor Medium

1/**
2 * [1026] Maximum Difference Between Node and Ancestor
3 *
4 * 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.
5 * 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.
6 *  
7 * Example 1:
8 * <img alt="" src="https://assets.leetcode.com/uploads/2020/11/09/tmp-tree.jpg" style="width: 400px; height: 390px;" />
9 * Input: root = [8,3,10,1,6,null,14,null,null,4,7,13]
10 * Output: 7
11 * Explanation: We have various ancestor-node differences, some of which are given below :
12 * |8 - 3| = 5
13 * |3 - 7| = 4
14 * |8 - 1| = 7
15 * |10 - 13| = 3
16 * Among all possible differences, the maximum value of 7 is obtained by |8 - 1| = 7.
17 * Example 2:
18 * <img alt="" src="https://assets.leetcode.com/uploads/2020/11/09/tmp-tree-1.jpg" style="width: 250px; height: 349px;" />
19 * Input: root = [1,null,2,null,0,3]
20 * Output: 3
21 * 
22 *  
23 * Constraints:
24 * 
25 * 	The number of nodes in the tree is in the range [2, 5000].
26 * 	0 <= Node.val <= 10^5
27 * 
28 */
29pub struct Solution {}
30use crate::util::tree::{TreeNode, to_tree};
31
32// problem: https://leetcode.com/problems/maximum-difference-between-node-and-ancestor/
33// discuss: https://leetcode.com/problems/maximum-difference-between-node-and-ancestor/discuss/?currentPage=1&orderBy=most_votes&query=
34
35// submission codes start here
36
37// Definition for a binary tree node.
38// #[derive(Debug, PartialEq, Eq)]
39// pub struct TreeNode {
40//   pub val: i32,
41//   pub left: Option<Rc<RefCell<TreeNode>>>,
42//   pub right: Option<Rc<RefCell<TreeNode>>>,
43// }
44// 
45// impl TreeNode {
46//   #[inline]
47//   pub fn new(val: i32) -> Self {
48//     TreeNode {
49//       val,
50//       left: None,
51//       right: None
52//     }
53//   }
54// }
55use std::rc::Rc;
56use std::cell::RefCell;
57impl Solution {
58    pub fn max_ancestor_diff(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
59        0
60    }
61}
62
63// submission codes end
64
65#[cfg(test)]
66mod tests {
67    use super::*;
68
69    #[test]
70    fn test_1026() {
71    }
72}
73