python - Python recursion didn't give correct result for "sum of left leaves"

Question

I wrote a code for the leetcode problem "108. Sum of Left Leaves" using recursion. It didn't give me the expected result.

# 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

When the input is [3,9,20,null,null,15,7]

I expected a 24 to be returned, but the code only gave me 9

标签： pythonrecursionbinary-tree

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