In a binary tree T, a path P is a non-empty sequence of nodes of tree such that, each consecutive node in the sequence is a subtree of its preceding node. In the example tree, the sequences [9, 8, 2] and [5, 8, 12] are two paths, while [12, 8, 2] is not. The amplitude of path P is the maximum difference among values of nodes on path P. The amplitude of tree T is the maximum amplitude of all paths in T. When the tree is empty, it contains no path, and its amplitude is treated as 0. For exmaple.

Input: 5 / \ 8 9 / \ / \ 12 2 8 4 / / 2 5 Output: 7 Explanation: The paths [5, 8, 12] and [9, 8, 2] have the maximum amplitude 7.

Naive Thinking: 关键句是The amplitude of path P is the maximum difference among values of nodes on path P. 可以采用DFS，记录一条路径上的最大值和最小值，求差值，最后再总的求一个最大值。

算法复杂度是 O(n), space O(n)。

也可以用一个全局变量去记录max, 那样就不需要最后再总的求一次最大值。

Source from :http://massivealgorithms.blogspot.com/2016/01/non-leetcode-questions-amplitude-of-tree.html

public int MaxDiff(TreeNode root){
  if(root==0) return 0;
  return dfs(root,root.val,root.val);
}

public static int dfs(TreeNode root, int min, int max){
   if(root==null)
   return max-min;
   min = Math.min(min,root.val);
   max = Math.max(max,root.val);
   return Math.max(dfs(root.left,min,max),dfs(root.right,min,max));  
}