Deepest Leaves Sum
环境：python 3.6，scala 2.11.8，A song

题意

标题即题意，返回二叉树中层数最深的叶子节点的和。

分析

• 基础：要求掌握二叉树的层序遍历；

• 区别：只需记录最深一层的叶子结点即可，代码更简洁；

代码

python

import collections


def deepestLeavesSum(root):
    """
    :type root: TreeNode
    :rtype: int
    """
    if not root: return 0

    res = collections.defaultdict(list)

    def dfs(node, depth):
        if node:
            res[depth].append(node.val)
            dfs(node.left, depth + 1)
            dfs(node.right, depth + 1)

    dfs(root, 0)

    max_key = max(res.keys())

    return sum(res[max_key])

# 无需记录过程中的结点值，这里可简化 LC102 - levelOrderV3
def deepestLeavesSumV2(root):
    if not root: return 0

    queue = [root]
    while queue:
        previous, queue = queue, [child for node in queue for child in [node.left, node.right] if child]

    return sum(node.val for node in previous)

scala

import scala.collection.mutable.Queue

object LC1302 {

  def deepestLeavesSum(root: TreeNode): Int = {
    if (root == null) return 0
    val queue = Queue[TreeNode](root)
    var previous = List.empty[TreeNode]

    while (queue.nonEmpty) {
      previous = queue.toList
      (1 to queue.size) foreach {_ =>
        val curr = queue.dequeue()
        if (curr.left != null) queue.enqueue(curr.left)
        if (curr.right != null) queue.enqueue(curr.right)
      }
    }
    previous.map(_.value).sum
  }

  def deepestLeavesSumV2(root: TreeNode): Int = {
    def go(currLevel: List[TreeNode], previous: List[TreeNode]): List[TreeNode] = {
      if (currLevel.isEmpty) previous
      else {
        val nextLevel = currLevel.flatMap{node => List(node.left, node.right).filter(_!=null)}
        go(nextLevel, currLevel)
      }
    }
    go(if (root == null) Nil else List(root), Nil).map(_.value).sum
  }
}

最后

欢迎交流和补充