# 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:**

![](https://3979976701-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MWCWmbVhbhatBCAMIGH%2Fuploads%2Fgit-blob-1ee2edac5921f6fb7392c3e3fb56ef822528431a%2Fimage%20\(22\).png?alt=media)

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