Amplitude of Tree

From http://codesays.com/2014/solution-to-tree-amplitude/

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, 那样就不需要最后再总的求一次最大值。 

 class TreeNode{  
   int val;  
   TreeNode left, right;  
   TreeNode(int x){  
     val = x;  
     left = null;  
     right = null;  
   }  
 }  
 public int amplitudeOfTree(TreeNode root){  
     if(root==null) return 0;  
     int max = 0;  
     List<Integer> maxs = new ArrayList<Integer>();  
     // use a List<Integer> to record min and max along a path  
     List<Integer> list = new ArrayList<Integer>();  
     list.add(root.val);  
     list.add(root.val);  
     dfs(root,list,maxs);  
     for(int i = 0;i < maxs.size();i++)  
       max = Math.max(maxs.get(i),max);  
     return max;  
   }  
   private void dfs(TreeNode root, List<Integer> cur, List<Integer> maxs){  
     if(root.left==null && root.right==null) maxs.add(cur.get(1)-cur.get(0));  
     if(root.left != null){  
       List<Integer> list = new ArrayList<Integer>(cur);  
       if(root.left.val < list.get(0)) list.set(0,root.left.val);  
       if(root.left.val > list.get(1)) list.set(1,root.left.val);  
       dfs(root.left, list, maxs);  
     }  
     if(root.right != null){  
       List<Integer> list = new ArrayList<Integer>(cur);  
       if(root.right.val < list.get(0)) list.set(0,root.right.val);  
       if(root.right.val > list.get(1)) list.set(1,root.right.val);  
       dfs(root.right, list, maxs);  
     }  
     return;  
   }