LeetCode 1302. Deepest Leaves Sum

September 14, 2020

This looks like an $O(n)$ breadth-first tree traversal where we sum the values of the last row. Maybe we do this by overwriting the sum of each row in the same variable and returning it at the end?

Actually, instead of summing every row, we can tell we're on the last row if our 'next' row for breadth-first iteration is empty. We can just return the sum of that row.

We can't do better than $O(n)$ since finding every node in the deepest row requires traversing all paths in the tree.

from typing import List
import unittest

from .. import TreeNode

class Test(unittest.TestCase):

    def setUp(self):
        self.s = Solution()

    def test_examples(self):
        t = TreeNode.from_list([1,2,3,4,5,None,6,7,None,None,None,None,None,None,8])
        self.assertEqual(self.s.deepestLeavesSum(t), 15)

    def test_single(self):
        t = TreeNode.from_list([3])
        self.assertEqual(self.s.deepestLeavesSum(t), 3)

    def test_right(self):
        t = TreeNode.from_list([3,None,2])
        self.assertEqual(self.s.deepestLeavesSum(t), 2)
        t = TreeNode.from_list([3,None,2,None,None,None,1,None,None,None,None,None,None,None,7])
        self.assertEqual(self.s.deepestLeavesSum(t), 7)

    def test_left(self):
        t = TreeNode.from_list([3,2,None])
        self.assertEqual(self.s.deepestLeavesSum(t), 2)
        t = TreeNode.from_list([3,2,None,1,None,None,None,7,None,None,None,None,None,None,None])
        self.assertEqual(self.s.deepestLeavesSum(t), 7)

class Solution:

    def deepestLeavesSum(self, root: TreeNode) -> int:
        q = [root]
        while q:
            nextq = []
            for n in q:
                if n.left:
                    nextq.append(n.left)
                if n.right:
                    nextq.append(n.right)
            if not nextq:
                break
            q = nextq
        return sum([n.val for n in q])

if __name__ == "__main__":
    unittest.main()