解法一：广度优先遍历

对于每一层结点都进行求和，但只保留最近一次结果，最后输出的就是最后一层的结点之和。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. /**
  11.  * Definition for a binary tree node.
  12.  * public class TreeNode {
  13.  * int val;
  14.  * TreeNode left;
  15.  * TreeNode right;
  16.  * TreeNode(int x) { val = x; }
  17.  * }
  18.  */
  19. class Solution {
  20.     public int deepestLeavesSum(TreeNode root) {
  21.         Queue<TreeNode> queue = new LinkedList<>();
  22.         if (root != null) {
  23.             queue.offer(root);
  24.         }
  25.         // 记录每一层的结点之和, 只保留最近一次结果
  26.         int sum = 0;
  27.         while (!queue.isEmpty()) {
  28.             int size = queue.size();
  29.             sum = 0;
  30.             for (int i = 0; i < size; ++i) {
  31.                 TreeNode tmp = queue.poll();
  32.                 sum += tmp.val;
  33.                 if (tmp.left != null) {
  34.                     queue.offer(tmp.left);
  35.                 }
  36.                 if (tmp.right != null) {
  37.                     queue.offer(tmp.right);
  38.                 }
  39.             }
  40.         }
  41.         return sum;
  42.     }
  43. }

解法二：深度优先遍历

由于事先不知道树的深度（除非先进行一遍遍历），因此要在遍历过程中根据当前深度来维护最大深度和结点之和这两个成员变量。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  * int val;
  5.  * TreeNode left;
  6.  * TreeNode right;
  7.  * TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  11. /**
  12.  * Definition for a binary tree node.
  13.  * public class TreeNode {
  14.  * int val;
  15.  * TreeNode left;
  16.  * TreeNode right;
  17.  * TreeNode(int x) { val = x; }
  18.  * }
  19.  */
  20. class Solution {
  21.     /**
  22.      * 最大深度
  23.      */
  24.     private int maxDepth;
  26.     /**
  27.      * 最深层叶子结点之和
  28.      */
  29.     private int sum;
  31.     public int deepestLeavesSum(TreeNode root) {
  32.         maxDepth = 0;
  33.         sum = 0;
  34.         dfs(root, 1);
  35.         return sum;
  36.     }
  38.     private void dfs(TreeNode root, int depth) {
  39.         if (root == null) {
  40.             return;
  41.         }
  42.         // 没有左右子树, 说明是叶子结点
  43.         if ((root.left == null) && (root.right == null)) {
  44.             // 比原先记录的最大深度大, 更新最大深度, 之前的求和作废
  45.             if (depth > maxDepth) {
  46.                 maxDepth = depth;
  47.                 sum = root.val;
  48.             } else if (depth == maxDepth) { // 等于当前最大深度, 求和
  49.                 sum += root.val;
  50.             } else { // 比最大深度小, 忽略
  51.                 return;
  52.             }
  53.         }
  55.         if (root.left != null) {
  56.             dfs(root.left, depth + 1);
  57.         }
  58.         if (root.right != null) {
  59.             dfs(root.right, depth + 1);
  60.         }
  61.     }
  62. }