二叉树叶子值的总和

Question

我写了这段代码，当我使用 print 时，我看到我得到了树叶。但是，函数的最终 return 是 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))

Answer 1

您在对分支 (left/right) 求和时忘记添加 +，而且您还忘记访问 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)

Answer 2

您没有将总和相加或返回。这也可以通过 class:

中的方法来完成

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

    def sum(self):
        s = 0
        if self.left is not None:
            s += self.left.sum()
        if self.right is not None:
            s += self.right.sum()
        return self.val + s


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

print(node.sum())

returns:

Answer 3

您没有正确返回计算出的叶总和。试试这个：

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

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

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

    elif tree.right is None and tree.left is None:
        return tree.val

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

print(sum_leafs(node))

Answer 4

节点

首先，我将更新您的Node界面，以便在创建节点时可以设置left和right分支-

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

这使我们能够更符合人体工程学地创建树木，例如 -

t = Node(10, Node(11, None, Node(5)), Node(2))

遍历

现在我们编写一个通用遍历程序。这允许我们将 1) 树的遍历与 2) 我们想要对每个树元素执行的预期操作分开 -

def traverse(tree):
  if tree is None:
    return
  else:
    yield tree.val
    yield from traverse(tree.left)
    yield from traverse(tree.right)

现在 sum_leafs 的需求消失了。我们已经将遍历逻辑与求和逻辑分离。我们可以用 sum 和 traverse -

的简单组合来计算叶子的总和

print(sum(traverse(t)))
# 28

不要重复自己

或者，我们可以编写一个 search 函数来查找传递谓词的第一个值 -

，而不是对这些值求和

def search(test, tree):
  for val in traverse(tree):
    if test(val):
      return val

print(search(lambda x: x < 10, t))
# 5

print(search(lambda x: x > 99, t))
# None

或者，我们可以简单地将每个值收集到一个列表中 -

print(list(traverse(t)))
# [ 10, 11, 5, 2 ]

如您所见，从依赖于我们的树的每个函数中删除遍历逻辑可能会有很大帮助。

无发电机

如果您不喜欢生成器，您可以编写 traverse 的 eager 版本，它总是 returns 一个 list。现在的区别是没有办法部分遍历树。请注意此程序与生成器版本的相似之处 -

def traverse(t):
  if t is None:
    return [] # <-- empty
  else:
    return \
      [ t.val
      , *traverse(t.left)  # <-- yield from
      , *traverse(t.right) # <-- yield from
      ]

print(traverse(t))
# [ 10, 11, 5, 2 ]

二叉树叶子值的总和

Sum of binary tree leaves' values

python

recursion

binary-tree