The number of nodes in the tree is in the range [1, 104].
1 <= Node.val <= 100
Solutions
Solution 1: BFS
We can use breadth-first search (BFS) to traverse the binary tree level by level, and calculate the sum of the node values at each level. After completing the traversal, return the sum of the node values at the last level.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the number of nodes in the tree.
1 2 3 4 5 6 7 8 910111213141516171819
# 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 = rightclassSolution:defdeepestLeavesSum(self,root:Optional[TreeNode])->int:q=deque([root])whileq:ans=0for_inrange(len(q)):node=q.popleft()ans+=node.valifnode.left:q.append(node.left)ifnode.right:q.append(node.right)returnans
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcdeepestLeavesSum(root*TreeNode)(ansint){q:=[]*TreeNode{root}forlen(q)>0{ans=0fork:=len(q);k>0;k--{node:=q[0]q=q[1:]ans+=node.Valifnode.Left!=nil{q=append(q,node.Left)}ifnode.Right!=nil{q=append(q,node.Right)}}}return}
We can use depth-first search (DFS) to recursively traverse the binary tree while keeping track of the current node's depth, the maximum depth, and the sum of the deepest leaf nodes. When visiting the current node, if the current node's depth equals the maximum depth, add the current node's value to the sum of the deepest leaf nodes. If the current node's depth is greater than the maximum depth, update the maximum depth to the current node's depth and update the sum of the deepest leaf nodes to the current node's value.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the number of nodes in the tree.
1 2 3 4 5 6 7 8 91011121314151617181920212223
# 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 = rightclassSolution:defdeepestLeavesSum(self,root:Optional[TreeNode])->int:defdfs(root,i):nonlocalans,mxifrootisNone:returnifi==mx:ans+=root.valelifi>mx:ans=root.valmx=idfs(root.left,i+1)dfs(root.right,i+1)ans=mx=0dfs(root,1)returnans
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcdeepestLeavesSum(root*TreeNode)int{ans,mx:=0,0vardfsfunc(*TreeNode,int)dfs=func(root*TreeNode,iint){ifroot==nil{return}ifi==mx{ans+=root.Val}elseifi>mx{mx=ians=root.Val}dfs(root.Left,i+1)dfs(root.Right,i+1)}dfs(root,1)returnans}