Given a binary tree, return the sum of values of its deepest leaves.
 
Example 1:

Input: root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
Output: 15

 
Constraints:

The number of nodes in the tree is between 1 and 10^4.
The value of nodes is between 1 and 100.

Difficulty: interview

Starter code:

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right
class Solution:
    def deepestLeavesSum(self, root: TreeNode) -> int:
        

Solutions:
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def deepestLeavesSum(self, root: TreeNode) -> int:
        q = [root]
        while q:
            pre, q = q, [child for p in q for child in [p.left, p.right] if child]
        return sum(node.val for node in pre)
       
            


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    node_sum = 0
    most_depth = 0
    
    def deepestLeavesSum(self, root: TreeNode) -> int:
        depth = 0
        self.generate_deepest_node_map(root, depth)
        return self.node_sum
            
    def generate_deepest_node_map(self, node, depth):
        if node:
            if node.left:
                self.generate_deepest_node_map(node.left, depth + 1)
            if node.right:
                self.generate_deepest_node_map(node.right, depth + 1)
            if not node.right and not node.left:
                if self.most_depth == depth:
                    self.most_depth = depth
                    self.node_sum += node.val
                if self.most_depth < depth:
                    self.most_depth = depth
                    self.node_sum = node.val
                
            



# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
from collections import defaultdict
class Solution:
    def deepestLeavesSum(self, root: TreeNode) -> int:
        treeDict = defaultdict(list)
        
        def treeLevel(root, level):
            if not root:
                return 
            else:
                treeDict[level].append(root.val)
                
            treeLevel(root.left, level+1)
            treeLevel(root.right, level+1)
            
        treeLevel(root, 0)
        
        return sum(treeDict[list(treeDict.keys())[-1]])

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def deepestLeavesSum(self, root: TreeNode) -> int:
        ### DFS?
        nxt = [(0,root)]
        tot = 0
        depth = 0
        while nxt: 
            d, cur = nxt.pop()
            if d == depth:
                tot += cur.val
            elif d > depth:
                tot = cur.val
                depth = d
            nxt.extend([(d+1,x) for x in [cur.left,cur.right] if x])
        return tot


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def deepestLeavesSum(self, root: TreeNode) -> int:
        s = {}

        def check(root, depth, s):
            if root == None:
                return 0
            
            if depth not in s:
                s[depth] = [root.val]
            else:
                s[depth].append(root.val)
                
            check(root.left, depth+1, s)
            check(root.right, depth+1, s)
            
            return s
        
        check(root, 0, s)
        
        m = max(s.keys())
        
        return sum(s[m])

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def deepestLeavesSum(self, root: TreeNode) -> int:
        if not root:
            return 0
        
        this_q = [root]
        result = 0
        
        while this_q:
            next_q = []
            temp = 0
            for node in this_q:
                temp += node.val
                if node.left:
                    next_q.append(node.left)
                if node.right:
                    next_q.append(node.right)
            
            this_q = next_q
            result = max(0, temp)
            
        return result

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def deepestLeavesSum(self, root: TreeNode) -> int:
        #zoe  bfs
        # s = 0
        # q = deque()
        # temp = []
        # if root == None:
        #     return s
        # q.append(root)
        # while q:
        #     node = q.pop()
        #     s += node.val
        #     if node.left: temp.append(node.left)
        #     if node.right: temp.append(node.right)
        #     if not q:
        #         if not temp:
        #             return s
        #         else:
        #             q.extend(temp)
        #             temp = []
        #             s = 0
        # return
        
        q = [root]
        while q:
            pre, q = q, [child for p in q for child in [p.left, p.right] if child]
        return sum(node.val for node in pre)
        
        


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def deepestLeavesSum(self, root: TreeNode) -> int:
        
        def maxDepth(rt):
            root=rt
            if root ==None:
                return 0
            #print(root)
            stack_list=[(root,1)]
            maxh=1
            if root.left==None and root.right==None:
                return maxh


            while len(stack_list)!=0:

                r,v=stack_list.pop()
                #print(r)
                #print(v)
                if r.right==None and r.left==None:
                    #stack_list.append()
                    if v>maxh:
                        maxh=v


                if r.left!=None:
                    #v=v+1
                    stack_list.append((r.left,v+1))
                if r.right!=None:
                    #v=v+1
                    stack_list.append((r.right,v+1))
            return maxh
        htmax=maxDepth(root)
        
        if htmax==0:
            return 0
        #stack=[root]
        
        stack_list=[(root,1)]
        #maxh=1
        dmax=0
        if root.left==None and root.right==None:
            return root.val

        maxh=1
        while len(stack_list)!=0:

            r,v=stack_list.pop()
            #print(r)
            #print(v)
            if r.right==None and r.left==None:
                #stack_list.append()
                if v>maxh:
                    maxh=v


            if r.left!=None:
                #v=v+1
                stack_list.append((r.left,v+1))
                if v+1==htmax:
                    dmax=dmax+r.left.val
                
            if r.right!=None:
                #v=v+1
                stack_list.append((r.right,v+1))
                if v+1==htmax:
                    dmax=dmax+r.right.val
        return dmax
        
        
        
        
        
            


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def deepestLeavesSum(self, root: TreeNode) -> int:
        s = 0
        q = deque()
        temp = deque()
        if root == None:
            return s
        q.append(root)
        while q:
            node = q.pop()
            s += node.val
            if node.left: temp.append(node.left)
            if node.right: temp.append(node.right)
            if not q:
                if not temp:
                    return s
                else:
                    q = temp
                    temp = deque()
                    s = 0
        return
        
        


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def deepestLeavesSum(self, root: TreeNode) -> int:
        if not root:
            return None
        queue = []
        queue.append(root)
        result = []
        while len(queue) > 0:
            levellength = len(queue)
            temp = []
            for i in range(levellength):
                node = queue.pop(0)
                temp.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            if len(temp) > 0:
                result.append(temp)
        return sum(result[-1])

from collections import namedtuple


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


leaf_info = namedtuple(\"Leaf_Info\", \"depth sum\")


class Solution:
    def deepestLeavesSum(self, root: TreeNode) -> int:
        def is_leaf(node: TreeNode) -> bool:
            return node.left is None and node.right is None

        def leaves(node: TreeNode, depth: int, path_sum: int) -> leaf_info:
            if node is None:
                yield leaf_info(0, 0)
            elif is_leaf(node):
                yield leaf_info(depth, node.val)
            else:
                yield from leaves(node.left, depth + 1, path_sum)
                yield from leaves(node.right, depth + 1, path_sum)
        
        max_depth = 0
        leaves_sum = 0
        for leaf in leaves(root, 0, 0):
            if leaf.depth > max_depth:
                max_depth, leaves_sum = leaf
            elif leaf.depth == max_depth:
                leaves_sum += leaf.sum

        return leaves_sum


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def deepestLeavesSum(self, root: TreeNode) -> int:
        # s = 0
        # q = deque()
        # temp = []
        # if root == None:
        #     return s
        # q.append(root)
        # while q:
        #     node = q.pop()
        #     s += node.val
        #     if node.left: temp.append(node.left)
        #     if node.right: temp.append(node.right)
        #     if not q:
        #         if not temp:
        #             return s
        #         else:
        #             q.extend(temp)
        #             temp = []
        #             s = 0
        # return
        
        q = [root]
        while q:
            pre, q = q, [child for p in q for child in [p.left, p.right] if child]
        return sum(node.val for node in pre)
        
        


# Definition for a binary tree node.\r
# class TreeNode:\r
#     def __init__(self, val=0, left=None, right=None):\r
#         self.val = val\r
#         self.left = left\r
#         self.right = right\r
class Solution:\r
    def deepestLeavesSum(self, root: TreeNode) -> int:\r
        currentLevel = [root]\r
        while currentLevel:\r
            currentSum = 0\r
            nextLevel = []\r
            for node in currentLevel:\r
                currentSum += node.val\r
                if node.left:\r
                    nextLevel.append(node.left)\r
                if node.right:\r
                    nextLevel.append(node.right)\r
            currentLevel = nextLevel\r
        return currentSum

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
import collections
class Solution:
    def deepestLeavesSum(self, root: TreeNode) -> int:
        total, maxLevel = 0, 0
        def helper(node, level):
            if not node:
                return
            nonlocal total
            nonlocal maxLevel
            print((total, maxLevel, node.val, level))
            if level > maxLevel:
                print(('here', level, maxLevel))
                total = node.val
                maxLevel = level
            elif level == maxLevel:
                total += node.val
            
            helper(node.left, level + 1)
            helper(node.right, level + 1)
        
        
        helper(root, 0)
        print(total)
        return total
    
            

           
        
        


import queue
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def deepestLeavesSum(self, root: TreeNode) -> int:
        q = queue.deque()
        q.append(root)
        ans = 0
        while q:
            ans = 0
            for _ in range(len(q)):
                cur_node = q.popleft()
                ans += cur_node.val
                if cur_node.left:
                    q.append(cur_node.left)
                if cur_node.right:
                    q.append(cur_node.right)
        return ans


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def deepestLeavesSum(self, root: TreeNode) -> int:
        
        stack=[(root,0)]
        if not root:return 0
        leaf_nodes=[]
        max_depth,deepest_sum=0,0
        while stack:
            node,depth=stack.pop()
            
            if depth>max_depth:
                max_depth=depth
                deepest_sum=node.val
            elif depth==max_depth:
                deepest_sum+=node.val
            
            if node.right:
                stack.append((node.right,depth+1))
            if node.left:
                stack.append((node.left,depth+1))
                
        
        return deepest_sum
        
#         stack=[(root,0)]
#         if not root:return 0
#         leaf_nodes=[]
#         max_depth=0
#         while stack:
#             node,depth=stack.pop()
#             max_depth=max(max_depth,depth)
#             if not node.left and not node.right:
#                 leaf_nodes.append((node.val,depth))
            
#             if node.right:
#                 stack.append((node.right,depth+1))
#             if node.left:
#                 stack.append((node.left,depth+1))
                
#         sum_=0
#         for vals,depth in leaf_nodes:
#             if depth==max_depth:
#                 sum_+=vals
#         return sum_
                
        
                
            


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def deepestLeavesSum(self, root: TreeNode) -> int:
        
        def traverse(node: TreeNode, layer: int, nums: List[int]):
            if node is None:
                return
            
            while len(nums) < layer+1:
                nums.append([])
            nums[layer].append(node.val)
            
            traverse(node.left,layer+1,nums)
            traverse(node.right,layer+1,nums)
        
        by_layer = []
        
        traverse(root,0,by_layer)
        # print(by_layer)
        return sum(by_layer[-1])

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def deepestLeavesSum(self, root: TreeNode) -> int:
        if root is None:
            return 0
        queue=deque([(root,0)])
        res=defaultdict(list)
        while queue:
            top,l=queue.popleft()
            res[l].append(top.val)
            if top.left:
                queue.append((top.left,l+1))
            if top.right:
                queue.append((top.right,l+1))
        maxidx=max(sorted(res))
        return sum(res[maxidx])


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def deepestLeavesSum(self, root: TreeNode) -> int:
        self.sum_ = 0
        self.h = self.getHeight(root)
            
        self.helper(root, 1)
        return self.sum_
    def helper(self, node, height):
            if not node: return
            self.helper(node.left, height+1)
            self.helper(node.right, height+1)
            
            if height == self.h:
                self.sum_ += node.val
                
    def getHeight(self, node):
        if not node: return 0
        return 1 + max(self.getHeight(node.left), self.getHeight(node.right))

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def deepestLeavesSum(self, root: TreeNode) -> int:
        queue = deque([root])
        last_t = 0
        while queue:
            l_sum = 0
            for _ in range(len(queue)):
                node = queue.popleft()
                l_sum += node.val

                if node.left is not None:
                    queue.append(node.left)

                if node.right is not None:
                    queue.append(node.right)

            l_sum, last_t = 0, l_sum
            
        return last_t
        


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    
    def findDepth(self,root: TreeNode) -> int:
        if root == None:
            return 0
        if root.left == None and root.right == None:
            return 1
        return 1 + max(self.findDepth(root.left),self.findDepth(root.right))
    
    def deepestHelper(self,root: TreeNode,c: int, d: int) -> int:
        total = 0
        if root == None:
            return 0
        if c == d:
            return root.val
        return self.deepestHelper(root.left,c+1,d) + self.deepestHelper(root.right,c+1,d)
        
        
        
    def deepestLeavesSum(self, root: TreeNode) -> int:
        d = self.findDepth(root)
        return self.deepestHelper(root,1,d)


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


class Solution:
    def deepestLeavesSum(self, root: TreeNode) -> int:
        if not root:
            return 0
        q = [root]
        while True:
            q_new = [x.left for x in q if x.left]
            q_new += [x.right for x in q if x.right]
            if not q_new:
                break
            q = q_new
        return sum([node.val for node in q])


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def deepestLeavesSum(self, root: TreeNode) -> int:
        layer = 0
        total = [0]
        
        self.dfs(root, total, layer)
        print(total)
        return total[len(total)-1]
        
    def dfs(self, node, total, layer):
        if layer > len(total) - 1:
            total.append(0)
        if not node.left and not node.right:
            total[layer] += node.val
        
        if node.left:
            self.dfs(node.left, total, layer + 1)
        if node.right:
            self.dfs(node.right, total, layer + 1)


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


##### Stack DFS solution
# class Solution:
    
#     def deepestLeavesSum(self, root: TreeNode) -> int:

#         def isLeaf(node) -> bool:
#             return node.left is None and node.right is None

#         deepest_sum = 0
#         depth = 0
        
#         # Push root into stack
#         stack = [(root, 0)]
#         # while stack is not empty
#         while stack:
#             # Pop out a node from the stack and update the current number
#             node, current_depth = stack.pop()
#             # If the node is a leaf
#             if isLeaf(node):
#                 # Update the deepest leaves sum deepest_sum
                
#                 # If we are at a deeper level                
#                 if depth < current_depth:
#                     deepest_sum = node.val # start a new sum
#                     depth = current_depth # note new depth
                
#                 elif depth == current_depth:
#                     deepest_sum += node.val # update existing sum
                    
#             else:
#             # Push right and left child nodes into stack (right first)
#                 if node.right:
#                     stack.append((node.right, current_depth + 1))
#                 if node.left:
#                     stack.append((node.left, current_depth + 1))
#         return deepest_sum
        
    
# Queue BFS Solution
class Solution:
    
    def deepestLeavesSum(self, root: TreeNode) -> int:


        
        next_level = deque([root,])
        
        while next_level:
            # prepare for the next level
            curr_level = next_level
            next_level = deque()
            
            for node in curr_level:
                if node.left:
                    next_level.append(node.left)
                if node.right:
                    next_level.append(node.right)
        
        return sum([node.val for node in curr_level])

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def deepestLeavesSum(self, root: TreeNode) -> int:
        \"\"\"
        (1) level-order
            replace until end then sum list
        \"\"\"
        q, deepest_sum = deque(), 0
        q.append(root)
        while len(q):
            i, deepest_sum = len(q), 0
            while i > 0:
                top = q.popleft()
                deepest_sum += top.val
                if top.left:
                    q.append(top.left)
                if top.right:
                    q.append(top.right)
                i -= 1
        return deepest_sum
            

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
from collections import deque
class Solution:
    def deepestLeavesSum(self, root: TreeNode) -> int:
        
        deep_sum=0
        depth=0
        
        queue=deque()
        queue.append([root,0])
        
        while queue:
            node, curr_depth=queue.popleft()
            
            # if leaf node
            if not node.left and not node.right:
                # if current depth is deep that depth, 
                # ex: initially going till end
                if depth < curr_depth:
                    deep_sum=node.val
                    depth=curr_depth
                else:
                    # nodes existing at same depth
                    deep_sum+=node.val
            else:
                if node.left:
                    queue.append([node.left, curr_depth+1])
                if node.right:
                    queue.append([node.right, curr_depth+1])
        return deep_sum

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
from collections import deque
class Solution:
    def bfs_helper(self, root):
        deep_sum=0
        depth=0
        
        queue=deque()
        queue.append([root,0])
        
        while queue:
            node, curr_depth=queue.popleft()
            
            # if leaf node
            if not node.left and not node.right:
                # if current depth is deep that depth, 
                # ex: initially going till end
                if depth < curr_depth:
                    deep_sum=node.val
                    depth=curr_depth
                else:
                    # nodes existing at same depth
                    deep_sum+=node.val
            else:
                if node.left:
                    queue.append([node.left, curr_depth+1])
                if node.right:
                    queue.append([node.right, curr_depth+1])
        return deep_sum
    
    def dfs_helper(self, root):
        deep_sum=0
        depth=0
        
        stack=list()
        stack.append([root,0])
        
        while stack:
            node, curr_depth=stack.pop()
            
            # if leaf node
            if not node.left and not node.right:
                # if current depth is deep that depth, 
                # ex: initially going till end
                if depth < curr_depth:
                    deep_sum=node.val
                    depth=curr_depth
                elif depth == curr_depth:
                    # nodes existing at same depth
                    deep_sum+=node.val
            else:
                if node.left:
                    stack.append([node.left, curr_depth+1])
                if node.right:
                    stack.append([node.right, curr_depth+1])
        return deep_sum
    def deepestLeavesSum(self, root: TreeNode) -> int:
        return self.dfs_helper(root)


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def deepestLeavesSum(self, root: TreeNode) -> int:
        self.sum = 0
        self.deepest_lvl = 0
        
        def bfs(root: TreeNode, lvl = 0):
            if root is None:
                return
            
            if root.left is None and root.right is None:
                print(root.val, lvl)
                if lvl > self.deepest_lvl:
                    self.sum = root.val
                    self.deepest_lvl = lvl
                
                elif lvl == self.deepest_lvl:
                    self.sum += root.val
                return 
            
            bfs(root.left, lvl + 1)
            bfs(root.right, lvl + 1)
            
        bfs(root)
        
        return self.sum