关于递归return语句顺序的问题

Question

我一直在研究一个问题，该问题计算二叉树上每个分支的总和并将它们 return 存储在一个数组中。它几乎是一个 DFS 问题，您可以在其中将解决方案累积到一个数组中。我只是在努力理解在我的代码中放置 return 语句的位置。我知道正确答案，只是不知道为什么下面这两个片段不等同：

 def branchTot(root):
    soln = []
    fin  = help(root, root.value, soln)
    return fin


def help(root, sums, soln): 
    if root.left is None and root.right is None:
        soln.append(sums)
        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)

和下面的第二个解决方案：

 def branchTot(root):
    soln = []
    fin  = help(root, root.value, soln)
    return fin


def help(root, sums, soln): 
    if root.left is None and root.right is None:
        soln.append(sums)


    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)

    return soln

Answer 1

如果一棵树只有一个节点（根节点），您的两种解决方案都可以使用。下面说说第一种方案：

您 return 仅在 children 都是 None 的情况下使用 soln 数组。现在，如果节点有一个或多个 children，此条件将始终失败。因此，return 语句永远不会执行。这就是原因，第一个解决方案是 returning 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 语句。这是 return 最终数组。

希望对您有所帮助。

关于递归return语句顺序的问题

Question about recursive return statement order

python

recursion

return-value

recursive-backtracking