IT TEST - 试试看，你能在40分钟内任选语言解决以下问题吗？

A binary tree is either an empty tree (represented by an empty pointer) or a node consisting of a single integer value and two binary trees called the left subtree and right subtree.

 

A binary tree T is given. A path in tree T is a non-empty sequence of nodes of tree T such that each consecutive node in the sequence is a subtree of its preceding node.

 

A path P in tree T is given. The amplitude of path P is the maximum difference between values of nodes on path P. The amplitude of tree T is the maximum amplitude of paths in T. If tree T is empty, then it does not have any paths and its amplitude is assumed to be 0.

 

For example, consider the following tree T consisting of nine nodes:

           5

 /  \

        8    9

       /  \   |  \

    12   2  8   4

              |    |

              2   5

 

Sequence [9, 8, 2] is a path in this tree. Sequence [12, 8, 2] is not a path in this tree. Path [5, 8, 2] has amplitude 6. Paths [9, 8, 2] and [5, 8, 12] have amplitude 7. The amplitude of the tree is 7, as no path in it has amplitude greater than [9, 8, 2] or [5, 8, 12].

 

Assume that the following declarations are given:

class Tree {

 public int x;

 public Tree l;

 public Tree r;

}

 

Write a function:

 

class Solution { public int solution(Tree T); }

 

that, given a tree T consisting of N nodes, returns the amplitude of T.

 

For example, given tree T shown in the example above, the function should return 7.

Assume that:

·    N is an integer within the range [0..1,000,000];

·    each element of tree T is an integer within the range [-1,000,000,000..1,000,000,000].

 

所有跟帖： 

• 简单 -SunnyT- ♂ (63 bytes) () 09/21/2014 postreply 01:26:56

• about 35 minutes -尔思- ♀ (2583 bytes) () 09/22/2014 postreply 13:27:47

• Good job. I will test code later. -delta101- ♂ (0 bytes) () 09/22/2014 postreply 18:58:31