使用 Lambda 的树叶总和 (Python)

Question

我正在尝试 return 左叶中值的总和。我的树是用这个接口定义的

class Tree(object):
  def __init__(self, x):
    self.value = x
    self.left = None
    self.right = None

我对 how/why 这个 lambda 函数完成这个任务感到困惑。有人可以解释一下 lambda 函数正在检查什么吗？

leftLeavesSum=g=lambda t,f=0:t and f*t.value*(t.left==t.right)+g(t.left,1)+g(t.right) or 0

谢谢！

Answer 1

这个答案会很长。不是因为它很复杂，而是因为我想尽可能简单地解释事情。

所以，让我们把答案分成三个部分：

这个 lambda 函数是如何工作的？
让我们尝试一个示例，看看它是否能正常工作
如果发现任何问题如何解决

第一部分

这个 lambda 函数是如何工作的？知道这一点的最好方法是将整个 lambda 分成简单的 if..else 条件，希望这些条件不言自明：

def g(t, f=0):
    if t:                               #checks if t is not None
        sum_left_branch = g(t.left,1)   #gets the sum of left branch
        sum_right_branch = g(t.right)   #gets the sum of right branch
        is_leaf_node = t.left==t.right  #1 if t is a leaf node (has no children)
        return (f*t.value)*is_leaf_node + sum_left_branch + sum_right_branch
    else:
        return 0

此函数使用 f 过滤值。如您所见，f 与 t.right 一起使用时为零，这使得右分支的 (f*t.value)*is_leaf_node 的值始终为零。

第二部分：

在下面的代码中，我将按以下形式创建一个简单的树，看看这个函数是否能正常工作：

#    __1
#   /   \
#  3     2
# / \
#4   5

parent = Tree(1)
brother = Tree(2)
me = Tree(3)
child1 = Tree(4)
child2 = Tree(5)
# set connections
parent.left = me
parent.right = brother
me.left = child1
me.right = child2

现在，让我们运行 parent 上的函数：

leftLeavesSum(parent)  #4

这是最左边叶节点的值child1 = Tree(4)。根据您的问题，您想要左分支上所有叶子的总和。因此，如果您没有计算 root，则该值应为 7；如果您计算了，则该值应为 8。

所以，我认为这个功能不能正常使用；这将我们引向第三部分

第三部分

以下是此函数的正确实现（在我看来），更改量最少：

def g(t, f=0):
    if t is not None:
        sum_left_branch = g(t.left,1)
        return (f*t.value) + sum_left_branch
    return 0

让我们使用与之前相同的 Tree 来尝试此功能：

# exclude the root
g(parent)    #7

# include the root
g(parent, 1) #8

使用 Lambda 的树叶总和 (Python)

Sum of Tree Leaves using Lambda (Python)

python

lambda

binary-tree

第一部分

第二部分：

第三部分