67: Binary tree maximum path sum

Дано не пустое бинарное дерево, найдите путь с максимальной суммой

Замечание: путь может идти от родительского узла к дочернему

 

Пример 1

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

Output: 11

Пояснение: 3 + 5 + 2 + 1

Пример 2

Input:     2   
          / \  
         5   3 

Output:  10

Пояснение: 2 + 5 + 3