问题描述
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
Example 2:
Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
Output: 19
Constraints:
- The number of nodes in the tree is in the range [1, 10^4].
- 1 <= Node.val <= 100
问题分析
问题比较简单，找到最大深度叶子节点的和。
因此，我们定义一个map，key为深度，value是一个slice，用来保存同一深度叶子节点的值。遍历完整棵树后，在map中我们得到了所有带深度信息的叶子节点。
此时，遍历map，获得最大深度值；然后对处于最大深度的叶子节点求和即可。
示例代码
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func deepestLeavesSum(root *TreeNode) int {
depth := 1
// depth ==> 叶子节点集合
m := make(map[int][]int)
travel(root, depth, m)
maxdepth := 1
// 找到最大深度
for k := range m {
if k > maxdepth {
maxdepth = k
}
}
ans := 0
for _, v := range m[maxdepth] {
ans += v
}
return ans
}
func travel(root *TreeNode, depth int, m map[int][]int) {
if root == nil {
return
}
// 如果是叶子节点，则append到对应depth的slice中
if root.Left == nil && root.Right == nil {
m[depth] = append(m[depth], root.Val)
return
}
if root.Left != nil {
travel(root.Left, depth+1, m)
}
if root.Right != nil {
travel(root.Right, depth+1, m)
}
}