1302. Deepest Leaves Sum
Medium | Tree + Level-order Traversal | 80 ms (98.31%), 17.7 MB (89.56%)
Source: LeetCode - Deepest Leaves Sum GitHub: Solution / Performance
Given the root
of a binary tree, return the sum of values of its deepest leaves.
Follow the level-order traversal, keep maintaining the sum of all nodes' values in the current level until the final iteration.
class Solution:
def deepestLeavesSum(self, root: TreeNode) -> int:
# (base case)
if not root.left and not root.right: return root.val
# ==================================================
# Binary Tree + Level Order Traversal =
# ==================================================
# time : O(n)
# space : O(n)
ans = 0
stack = [root]
while stack:
ans = 0
# loop through stack for current length, pop the first node
for i in range(len(stack)):
node = stack.pop(0)
ans += node.val
if node.left: stack.append(node.left)
if node.right: stack.append(node.right)
return ans
Last updated
Was this helpful?