## Tuesday, January 5, 2016

### 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，记录一条路径上的最大值和最小值，求差值，最后再总的求一个最大值。

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