在递归中返回变量值

Question

我想返回树中所有左叶的值之和，但是当我的“total”变量返回给调用者时，它的值似乎丢失了。我能知道解决这个问题的办法吗

# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sumOfLeftLeaves(self, root: TreeNode) -> int:
        total = 0
        if root is None:
            return 0
        if root.left:
            sum1 = self.getLeftSum(root.left, total)
        if root.right:
            sum2 = self.getLeftSum(root.right, total)
        return sum1 + sum2

    def getLeftSum(self, cur_node, total):
        if cur_node.left:
            self.getLeftSum(cur_node.left, total)
        if cur_node.left is None and cur_node.right is None:
            total += cur_node.val
        return total

Answer 1

我认为这是一对相互交织的递归函数：

class Solution:
    def sumOfLeftLeaves(self, node):
        total = 0

        if node:
            if node.left:
                total += self.sumOfLeftLeaf(node.left)

            return total + self.sumOfLeftLeaves(node.right)

        return total

    def sumOfLeftLeaf(self, node):
        total = node.val

        if node.left:
            total += self.sumOfLeftLeaf(node.left)

        return total + self.sumOfLeftLeaves(node.right)

一个是通用节点处理程序，另一个专门处理左手节点

Answer 2

这个答案假设您希望对发生在left分支中的每个val求和。我们希望求和的数字如下所示(n)-

#        6
#       / \
#     (5)  8
#     /   / \
#   (3) (4)  9
#   / \     / 
# (1)  7  (2)

使用TreeNode类，我们构建my_tree-

my_tree = \
  TreeNode \
    ( 6
    , TreeNode
        ( 5
        , TreeNode(3, TreeNode(1), TreeNode(7))
        , None
        )
    , TreeNode
        ( 8
        , TreeNode(4)
        , TreeNode(9, TreeNode(2), None)
        )
    )

递归是一种函数遗产，因此将其与函数风格结合使用会产生最好的结果。这意味着避免突变、变量重新分配和其他副作用。我们可以将sum_left作为一个普通函数写入TreeNode-

def sum_left (t, is_left=False):
  if not t:
    return 0
  else:
    return \
      (t.val if is_left else 0) \
      + sum_left(t.left, True)  \
      + sum_left(t.right, False)

这是下面说同样事情的不那么冗长的方式-

def sum_left (t, is_left=False):
  if not t:
    return 0
  elif is_left:
    return t.val + sum_left(t.left, True) + sum_left(t.right, False)
  else:
    return 0 + sum_left(t.left, True) + sum_left(t.right, False)

现在让我们看看计算的sum_left

print(sum_left(my_tree))
# 5 + 3 + 1 + 4 + 2

=> 15

---

另一种选择是使用mutual recursion-

def sum_left (t):
  if not t:
    return 0
  else:
    return t.val + sum_left(t.left) + sum_right(t.right)

def sum_right (t):
  if not t:
    return 0
  else:
    return sum_left(t.left) + sum_right(t.right)

在这里，处理根节点的方式会有所不同。直接在根上调用sum_left也将对根节点求和-

print(sum_left(my_tree))
# 6 + 5 + 3 + 1 + 4 + 2

=> 21

如果要排除根节点，可以调用左节点上的sum_left和右分支上的sum_right

print(sum_left(my_tree.left) + sum_right(my_tree.right))
# 5 + 3 + 1 + 4 + 2

=> 15

或者，看似违反直觉，只需在my_tree上调用sum_right

print(sum_right(my_tree))
# 5 + 3 + 1 + 4 + 2

=> 15