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
and10^4
. - The value of nodes is between
1
and100
.
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)