leetcode链接：https://leetcode-cn.com/problems/deepest-leaves-sum/

题目描述：

给你一棵二叉树的根节点 root ，请你返回 层数最深的叶子节点的和 。


思路1: 两次递归

最直接的思路是 1: 先得到树的最大深度；2: 将最大深度的节点值相加。这样需要两次递归。

  1. func deepestLeavesSum(root *TreeNode) int {
  2.     //最大深度
  3.     depth := deepestDepth(root)
  5.         //最大深度叶子结点
  6.     nums := []int{}
  7.     findDeepest(root, &nums, depth)
  9.         //相加求和
  10.     var result int
  11.     for _, n := range nums {
  12.         result += n
  13.     }
  14.     return result
  15. }
  17. //获取最大深度的叶子结点
  18. func findDeepest(root *TreeNode, nums *[]int, depth int) {
  19.     if root == nil {
  20.         return
  21.     }
  22.     if depth == 1 {
  23.         if root != nil {
  24.             *nums = append(*nums, root.Val)
  25.         }
  26.     }
  27.     findDeepest(root.Left, nums, depth - 1)
  28.     findDeepest(root.Right, nums, depth - 1)
  29. }
  31. //获取最大深度
  32. func deepestDepth(root *TreeNode) int {
  33.     if root == nil {
  34.         return 0
  35.     }
  37.     if root.Left == nil && root.Right == nil {
  38.         return 1
  39.     }
  40.     depthLeft := deepestDepth(root.Left)
  41.     depthRight := deepestDepth(root.Right)
  42.     if depthLeft > depthRight {
  43.         return depthLeft + 1
  44.     } else {
  45.         return depthRight + 1
  46.     }
  47. }

思路2: 层序遍历

通过层序遍历的方式获取每一层叶子结点，计算最后一层结点的和。这个思路会有额外的空间浪费。

  1. func deepestLeavesSum(root *TreeNode) int {
  2.     //取出最后一层叶子结点加和
  3.     result := levelTree(root)
  4.     sum := 0
  5.     if len(result) > 0 {
  6.         for _, n := range result {
  7.             sum += n
  8.         }
  9.     }
  10.     return sum
  11. }
  13. //层序遍历，取出最后一层叶子结点
  14. func levelTree(root *TreeNode) []int {
  15.     var result [][]int
  16.     if root == nil {
  17.         return nil
  18.     }
  20.     level := []*TreeNode{root}
  21.     for len(level) > 0 {
  22.         var levelLeaves []int
  23.         levelTemp := []*TreeNode{}
  24.         for i := 0; i < len(level); i ++ {
  25.             levelLeaves = append(levelLeaves, level[i].Val)
  26.             if level[i].Left != nil {
  27.                 levelTemp = append(levelTemp, level[i].Left)
  28.             }
  29.             if level[i].Right != nil {
  30.                 levelTemp = append(levelTemp, level[i].Right)
  31.             }
  32.         }
  33.         level = levelTemp
  34.         result = append(result, levelLeaves)
  35.     }
  37.     if len(result) > 0 {
  38.         return result[len(result) - 1]
  39.     }
  40.     return []int{}
  41. }

思路3: 最优解 维护两个变量

递归求树的最大深度，同时维护两个全局变量 maxdep 和 sum，其中 maxdep表示搜索到的节点的最大深度，sum表示搜索到的深度等于 maxdep 的节点的权值之和。

  1. // sum为最终的和， maxdep为树的最大深度
  2. var sum, maxdep int
  4. func deepestLeavesSum(root *TreeNode) int {
  5.     sum, maxdep = 0, 0
  6.     deepestDepth(root, 0)
  7.     return sum
  8. }
  10. func deepestDepth(root *TreeNode, depth int) {
  11.     if root == nil {
  12.         return
  13.     }
  15.     if depth > maxdep {
  16.         maxdep = depth
  17.         sum = root.Val
  18.     } else if depth == maxdep {
  19.         sum += root.Val
  20.     }
  22.     deepestDepth(root.Left, depth + 1)
  23.     deepestDepth(root.Right, depth + 1)
  24. }