907. Maximum Difference Between Node and Ancestor

Given the root of a binary tree, return the maximum value of |a - b| over all pairs where a is an ancestor of b. Equivalently, for each root-to-node path track the minimum and maximum seen and maximize their spread. The tree is given as a level-order array.

Input: A level-order array of the tree.

Output: Integer — the maximum ancestor-descendant difference.

Examples

Input: [8,3,10,1,6,null,14,null,null,4,7,13]
Output: 7
Explanation: |8 - 1| = 7 is the largest.

Input: [1,null,2,null,0,3]
Output: 3
Explanation: |3 - 0| = 3.

Input: [2,1,3]
Output: 1
Explanation: Max difference is 1.

Constraints

• 2<=nodes<=5000
• 0<=value<=10^5

Asked by