67: Binary tree maximum path sum

Given a non empty binary tree, find out the path with a maximum sum

Note: a path can go down from parent to any child

 

Example 1

Input:       -8    
             / \
            2   3
           /   / \
         -4   5   1
             / 
            2 

Output: 11

Explanation: 3 + 5 + 2 + 1

Example 2

Input:     2   
          / \  
         5   3 

Output:  10

Explanation: 2 + 5 + 3