Вызов на 31 день — День 8

Проблема суммы путей III

Вам дано бинарное дерево, в котором каждый узел содержит целочисленное значение.

Найдите количество путей, которые в сумме дают заданное значение.

Путь не обязательно должен начинаться или заканчиваться в корне или листе, но он должен идти вниз (переходя только от родительских узлов к дочерним узлам).

В дереве не более 1000 узлов, а значения находятся в диапазоне от -1 000 000 до 1 000 000.

Пример:

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1
Return 3. The paths that sum to 8 are:
1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

Решение

Для своего решения я использовал два метода, которые вызываются рекурсивно:

• PathSum он вызывает PathSumFrom с каждым из узлов дерева.
• PathSumFrom смотрит, сколько путей из данного корня может суммировать искомое число.

Здесь вы можете увидеть производительность моего решения (имейте в виду, что время выполнения может варьироваться в зависимости от сервера):

Вы можете подписаться на меня в LinkedIn.