1302. Deepest Leaves Sum

LeetCode 1302. Deepest Leaves Sum

Description

Given the root of 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 in the range [1, 10^4].

• 1 <= Node.val <= 100

Tags

Tree, Depth-first Search

Solution

We can perform the DFS strategy to solve this. During searching, we also maintain a variable h to keep track of the current height we reach.

• h == max height, we add the current node's value onto the total value;

• h > max height, we update the max height along with the deepest leaf.

Complexity

• Time complexity: $O(n)$

• Space complexity: $O(h)$

Code

func deepestLeavesSum(root *TreeNode) int {
	ans, maxHeight := 0, -1
	var dfs func(node *TreeNode, h int)
	dfs = func(node *TreeNode, h int) {
		if node == nil {
			return
		}
		if h > maxHeight {
			maxHeight = h
			ans = node.Val // update max height along with the deepest leaf
		} else if h == maxHeight {
			ans += node.Val
		}
		dfs(node.Left, h+1)
		dfs(node.Right, h+1)
	}
	dfs(root, 0)
	return ans
}

Reference

1. 层数最深叶子节点的和