Sunday, July 16, 2017

Tree Amplitude

July 16, 2017

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.
Code:
public static int amplitude(TreeNode root) is answer, others are helper functions for testing.

Java code is here to study. 

No comments:

Post a Comment