Python计算二叉树的分支和

2024-03-29 08:52:37 发布

您现在位置:Python中文网/ 问答频道 /正文

所以我在解决一个algoExpert.io问题, 问题是写一个算法来计算从左到右的所有分支和。 问题是测试是否通过取决于我如何调用helper函数,我真的找不到原因

class BinaryTree:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def branchHelper(root, sums=[], branchSum=0):
    if root is None:
        return

    branchSum += root.value
    if root.left is None and root.right is None:
        sums.append(branchSum)

    branchHelper(root.left, sums, branchSum)
    branchHelper(root.right, sums, branchSum)
    return sums

到目前为止一切都很好

def branchSums(root): 

    sums = []                       #
    return branchHelper(root, sums) # Pass

从这张照片上可以看出,这工作得很好。 enter image description here

但一旦我这样做(这是我最初的解决方案):

def branchSums(root): 
    return branchHelper(root) # Fail

enter image description here

为什么使用默认和=[]会以这种方式失败

enter image description here

这是错误消息。 我可以看到测试用例使用了根1和左子3。 当我使用第二种方法时,我的代码会吐出[1,3]

我真的搞不懂这一点,任何帮助都将不胜感激


Tags: selfrightnonereturnifisvaluedef
1条回答
网友
1楼 · 发布于 2024-03-29 08:52:37

这是因为第二个sums参数具有默认值

如果你下次重写它,你就会通过考试

def branchHelper(root, sums=None, branchSum=0):
    if root is None:
        return

    if sums is None:
        sums = []

    branchSum += root.value
    if root.left is None and root.right is None:
        sums.append(branchSum)
    branchHelper(root.left, sums, branchSum)
    branchHelper(root.right, sums, branchSum)
    return sums

这是错误的一个例子:

def wrong_func(append_item, items=[]):
    items.append(append_item)
    return items

wrong_func(1) # output [1]
wrong_func(2) # output [1, 2]


def correct_func(append_item, items=None):
    if items is None:
        items = []
    items.append(append_item)
    return items

correct_func(1) # output [1]
correct_func(2) # output [2]

第一次调用该函数时,python会创建一个持久列表。每次后续的append调用都会将该值追加到原始列表中。这就是algoExpert.io测试代码时发生的情况

这就是为什么第一个测试通过,第二个测试失败(第一个测试二叉树有一个项目1,第二个测试用1,2进行下一次检查,它将新值附加到sums列表中,测试失败

相关问题 更多 >