Рекурсия Python не дала правильного результата для "суммы оставленных листьев"

Question

Я написал код для задачи leetcode "108. Sum of Left Leaves", используя рекурсию.Это не дало мне ожидаемого результата.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def sumOfLeftLeaves(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root is None:

            return 0

        ans = 0

        if root.left and not root.left.left and not root.left.right:

            ans += root.left.val


        self.sumOfLeftLeaves(root.left)
        self.sumOfLeftLeaves(root.right)

        return ans

Когда ввод [3,9,20, ноль, ноль, 15,7]

Я ожидал, что 24 будетвернулся, но код дал мне только 9

Answer 1

Вы не добавляете результаты листьев ниже корня. Вам нужно это:

class Solution(object):
    def sumOfLeftLeaves(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root is None:

            return 0

        ans = 0

        if root.left and not root.left.left and not root.left.right:
            ans += root.left.val

        ans += self.sumOfLeftLeaves(root.left) + self.sumOfLeftLeaves(root.right)

        return ans