49: Binary tree path sum

Дано бинарное дерево и сумма. Напишите метод для проверки существования пути от корня до любого листа дерева, при этом сумма узлов в пути должна быть равна данной сумме

 

Пример 1

Input:        1    sum = 15
             / \
            2   3
           /   /
          4   5  
             /  
            6 

Output: true

Пояснение: path 1->3->5->6

Пример 2

Input:     1   sum = 3
          / \  
         5   3 

Output: false