LeetCode 1026. Maximum Difference Between Node and Ancestor

原题链接在这里：https://leetcode.com/problems/maximum-difference-between-node-and-ancestor/

题目：

Given the?root?of a binary tree,find the maximum value?V?for which there exists?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: [8,3,10,1,6,null,14,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:

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

题解：

Perform DFS top down. On each level,Calculate maxmimum difference and update minimum and maximum value.

Time Complexity: O(n).

Space: O(h).

AC Java:

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 class Solution {
11     int res = 0;
12     
13     public int maxAncestorDiff(TreeNode root) {
14         if(root == null){
15             return res;
16         }
17         
18         dfs(root,root.val,root.val);
19         return res;
20     }
21     
22     private void dfs(TreeNode root,int min,int max){
23         if(root == null){
24             return;
25         }
26         
27         res = Math.max(res,Math.max(Math.abs(root.val - min),Math.abs(max-root.val)));
28         min = Math.min(min,root.val);
29         max = Math.max(max,root.val);
30         dfs(root.left,min,max);
31         dfs(root.right,max);
32     }
33 }