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
ais equal tob. - Any child of
ais an ancestor ofb.
Example 1
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13Input
root = [8,3,10,1,6,null,14,null,null,4,7,13]Output
7Among all possible ancestor-node differences, the maximum value is 7, obtained by
|8 - 1| = 7.Example 2
1
\
2
\
0
/
3Input
root = [1,null,2,null,0,3]Output
3The maximum ancestor-node difference in the tree is 3.
Constraints
- The number of nodes in the tree is in the range
[2, 5000]. 0 <= Node.val <= 10^5