1302. Deepest Leaves Sum #

Problem #

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.

Problem Summary #

Given a binary tree, return the sum of the leaf nodes at the deepest level.

Note:

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

Solution Ideas #

• Given a binary tree, return the sum of the leaf nodes at the deepest level.
• This problem is not difficult. Use DFS traversal to add up all leaf nodes at the bottom level.

Code #

func deepestLeavesSum(root *TreeNode) int {
	maxLevel, sum := 0, 0
	dfsDeepestLeavesSum(root, 0, &maxLevel, &sum)
	return sum
}

func dfsDeepestLeavesSum(root *TreeNode, level int, maxLevel, sum *int) {
	if root == nil {
		return
	}
	if level > *maxLevel {
		*maxLevel, *sum = level, root.Val
	} else if level == *maxLevel {
		*sum += root.Val
	}
	dfsDeepestLeavesSum(root.Left, level+1, maxLevel, sum)
	dfsDeepestLeavesSum(root.Right, level+1, maxLevel, sum)
}