Вопрос о порядке рекурсивного возврата

Оба ваших решения будут работать, если есть дерево только с одним узлом (корневым узлом). Теперь поговорим о первом решении:

• Вы возвращаете массив soln только в том случае, если оба дочерних элемента None. Теперь, если у узла есть один или несколько дочерних узлов, это условие всегда не выполняется. Следовательно, оператор return никогда не будет выполнен. И это причина, по которой первое решение возвращает None. Вот выполнение с использованием двоичного дерева поиска.

  class Tree:
      def __init__(self, val):
          self.value = val
          self.left = None
          self.right = None
  
      def add(self, val):
          if val <= self.value:
              if self.left is None:
                  self.left = Tree(val)
              else:
                  self.left.add(val)
          else:
              if self.right is None:
                  self.right = Tree(val)
              else:
                  self.right.add(val)
  
      def t_print(self):
          if self.left is not None:
              self.left.t_print()
          print self.value
          if self.right is not None:
              self.right.t_print()
  
  def help(root, sums, soln): 
     if root.left is None and root.right is None:
         soln.append(sums)
         print 'Returning value for node ' + str(root.value)
         return soln
  
     else:
          if root.right is not None and root.left is not None :
              help(root.left, sums + root.left.value, soln)
              help(root.right, sums + root.right.value, soln)
          elif root.right is not None:
              help(root.right, sums + root.right.value, soln)
          else:
              help(root.left, sums + root.left.value, soln)
      print 'Returning none for node ' + str(root.value)
      return None     # ----> This is what being executed after every recursive call finishes (for node with children)
  
  def branchTot(root):
      soln = []
      fin  = help(root, root.value, soln)
      return fin
  

Выполнение вышеуказанного даст следующий результат:

In [28]: root = Tree(9)
In [29]: root.add(5)
In [30]: root.add(3)
In [31]: root.add(2)
In [32]: root.add(10)
In [33]: root.add(13)
In [34]: root.add(11)


In [26]: branchTot(root)
Returning value for node 2
Returning none for node 3     ----> node with children
Returning none for node 5
Returning value for node 11    ------> node without children
Returning none for node 13
Returning none for node 10
Returning none for node 9

In [27]: 

Однако во втором решении вы взяли оператор return за пределы блока if, и, следовательно, оператор return выполняется, несмотря ни на что. Это возвращает последний массив.

Надеюсь это поможет.