python - 二叉树叶子值的总和

Question

我写了这段代码，当我使用 print 时，我看到我得到了叶子。但是，函数的最终返回值是None叶子的总和，而不是叶子的总和，这应该是7在这个例子中。我很高兴知道这里出了什么问题。谢谢 ！

class Node:
    def __init__(self, val=None):
        self.left = None
        self.right = None
        self.val = val


def sum_leafs(tree):
    if tree is None:
        return 0

    if tree.right and tree.left:
        sum_leafs(tree.right)
        sum_leafs(tree.left)

    elif tree.right or tree.left:
        if tree.right:
            sum_leafs(tree.right)
        elif tree.left:
            sum_leafs(tree.left)

    elif tree.right is None and tree.left is None:
        return sum_leafs(tree.left) + 1


node = Node(10)
node.right = Node(2)
node.left = Node(11)
node.left.right = Node(5)

print(sum_leafs(node))

标签： pythonrecursionbinary-tree

Answer 1

当您对分支（左/右）求和时忘记添加+，并且您忘记了访问val哪个是整个工作最关键的事情。

此外，逻辑可以简化：

def sum_leafs(tree):
    if tree is None:
        return 0

    if not tree.right and not tree.left:
        return tree.val

    return sum_leafs(tree.right) + sum_leafs(tree.left)