Non-Leetcode Questions: Amplitude of Tree

Non-Leetcode Questions: Amplitude of Tree
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, 那样就不需要最后再总的求一次最大值。 

https://cyqz.wordpress.com/2016/10/02/amazon-oa2-tree-amplitude-2/

public int Solution(TreeNode root) {
   if(root == null) return 0;
   return dfs(root, root.val, root.val);
  }
  public int dfs(TreeNode node, int min, int max) {
   if(node == null) {
    return max - min;
   }
   min = node.val < min ? node.val : min;
   max = node.val > max ? node.val : max;
   
   int left = dfs(node.left, min, max);
   int right = dfs(node.right, min, max);
   return Math.max(left, right);
  }

http://codingmelon.com/2015/12/11/amplitude-of-tree/

int getAmplitude (TreeNode* root) {

    if (root == NULL) {

        return 0;

    } else {

        return dfs(root, root->val, root->val);

    }

}

int dfs(TreeNode* root, int minn, int maxx) {

    minn = min(minn, root->val);

    maxx = max(maxx, root->val);

    if (root->left && root->right) {

        return max(dfs(root->left, minn, maxx), dfs(root->right, minn, maxx));

    }

    if (root->left) {

        return dfs(root->left, minn, maxx);

    }

    if (root->right) {

        return dfs(root->right, minn, maxx);

    }

    return maxx - minn;

}

http://siyang2notleetcode.blogspot.com/2015/02/amplitude-of-tree.html
Read full article from Non-Leetcode Questions: Amplitude of Tree