1302.Deepest Leaves Sum

In [1]:

import sys
sys.path.append("/home/swyoo/algorithm/")
from utils.verbose import buildtree
from binarytree import Node

1302. Deepest Leaves Sum

In [2]:

class Solution:
    def deepestLeavesSum(self, root: Node, verbose=False) -> int:
        maxlv, cands = 0, []
        def dfs(cur, lv):
            nonlocal maxlv
            if cur.left == cur.right == None:
                if lv >= maxlv:
                    maxlv = lv
                    cands.append((cur.value, lv))
                return
            if cur.left:
                dfs(cur.left, lv + 1)
            if cur.right:
                dfs(cur.right, lv + 1)
        dfs(root, 0)
        if verbose:
            root.pprint()
            print(cands, maxlv)
        return sum(x for x, lv in cands if lv == maxlv)

sol = Solution()

In [4]:

null = None
A = [1,2,3,4,5,null,6,7,null,null,null,null,8]
print(sol.deepestLeavesSum(buildtree(A), verbose=True))

      __1
     /   \
    2     3
   / \     \
  4   5     6
 /           \
7             8

[(7, 3), (8, 3)] 3
15