> For the complete documentation index, see [llms.txt](https://txfs19260817.gitbook.io/leetcode-go-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://txfs19260817.gitbook.io/leetcode-go-notes/solutions/1302.-deepest-leaves-sum.md).

# 1302. Deepest Leaves Sum

## LeetCode [1302. Deepest Leaves Sum](https://github.com/txfs19260817/LeetCode-Go/blob/master/solutions/title/README.md)

### Description

Given the `root` of a binary tree, return *the sum of values of its deepest leaves*.

**Example 1:**

![](/files/zkvIpeVQSqIPzYf5dM4W)

```
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

```go
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. [层数最深叶子节点的和](https://leetcode-cn.com/problems/deepest-leaves-sum/solution/ceng-shu-zui-shen-xie-zi-jie-dian-de-he-by-leetc-2/)