Python - 计算二叉树的分支和

Question

所以我正在解决一个 algoExpert.io 问题， 问题是编写一个算法来计算从左到右的所有分支总和。 问题是测试是否通过取决于我调用辅助函数的方式，我真的找不到原因。

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

从这张图片可以看出，这工作正常。

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

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

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

这是错误信息。 我可以看到测试用例使用了 root 1 和 left child 3。 当我使用第二种方法时，我的代码吐出 [1, 3]。

我真的无法理解这一点，我们将不胜感激。

Answer 1

这是因为您的第二个求和参数具有默认值。

如果你接下来重写它，你将通过测试

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 列表，并且你没有通过测试。