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

Read full article from Non-Leetcode Questions: Amplitude of Tree