开发者社区> 问答> 正文

关于递归返回语句顺序的问题

我一直在研究一个问题,计算一个二叉树的每个分支的和,并以数组的形式返回它们。这是一个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

问题来源StackOverflow 地址:/questions/59386467/question-about-recursive-return-statement-order

展开
收起
kun坤 2019-12-25 21:58:03 340 0
1 条回答
写回答
取消 提交回答
  • 如果树中只有一个节点(根节点),那么这两个解决方案都是有效的。现在我们来谈谈第一个解决方案: 执行以上将给出以下输出:

    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语句。这是返回最后一个数组。 希望这个有帮助。

    2019-12-25 21:58:13
    赞同 展开评论 打赏
问答地址:
问答排行榜
最热
最新

相关电子书

更多
低代码开发师(初级)实战教程 立即下载
冬季实战营第三期:MySQL数据库进阶实战 立即下载
阿里巴巴DevOps 最佳实践手册 立即下载