Maximum Difference Between Node and Ancestor

Given therootof a binary tree, find the maximum valueVfor which there existsdifferentnodesAandBwhereV = |A.val - B.val| andAis an ancestor ofB.

(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: 
[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.

Note:

The number of nodes in the tree is between 2 and 5000.
Each node will have value between 0 and 100000.

DFS

一条路上记录最大和最小即可

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def maxAncestorDiff(self, root: TreeNode,mx = float('-inf'),mn= float('inf')) -> int:
#         a,b = root.val,root.val
#         def dfs(root,mx,mn):            
#             if not root:
#                 return mx-mn
#             mx=max(mx,root.val)
#             mn = min(mn,root.val)
#             return max(dfs(root.left,mx,mn),dfs(root.right,mx,mn))


#         return dfs(root,a,b)
        return max(self.maxAncestorDiff(root.left,max(mx,root.val),min(mn,root.val)),self.maxAncestorDiff(root.right,max(mx,root.val),min(mn,root.val))) if root else mx-mn