## Description

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.

## Solutions

找到最后一层的所有叶子节点的加和。

### 1. BFS

# Time: O(nlogn)
# Space: O(n)
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def deepestLeavesSum(self, root: TreeNode) -> int:
if not root:
return 0
queue = collections.deque()
queue.append(root)
res = 0
while queue:
size = len(queue)
level_sum = 0
for _ in range(size):
node = queue.popleft()
if not node:
continue
level_sum += node.val
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
res = level_sum
return res

# 15/15 cases passed (96 ms)
# Your runtime beats 70.8 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (16.3 MB)