【LeetCode】层数最深叶子节点的和 Java 题解

作者：Albert

2022 年 8 月 17 日
北京
本文字数：1053 字
阅读完需：约 3 分钟

题目描述

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

示例 1：
输入：root = [1,2,3,4,5,null,6,7,null,null,null,null,8]输出：15
示例 2：
输入：root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]输出：19
来源：力扣（LeetCode）链接：https://leetcode.cn/problems/deepest-leaves-sum著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

今天的算法题目是二叉树的题目，题目要求返回层数最深的叶子节点的和。
分析题目之后，我们分为两步求解，第一步，确定当前的层的累加和，第二步，确定当前层是最深的层。如何求当前层的累加和呢？我们一般使用 BFS。BFS 全称是 Breadth First Search，中文名是宽度优先搜索，也叫广度优先搜索,是图上最基础、最重要的搜索算法之一。所谓宽度优先。就是每次都尝试访问同一层的节点。如果同一层都访问完了，再访问下一层。
在 Java 中，我们使用队列 Queue 来存储元素，完成 BFS 相关的功能，首先把 root 放入队列，然后每次计算出当前队列的长度，就是当前层元素的个数，逐个出队，完成当前层元素求和计算。
在使用 BFS 的过程中，已经完成了分层求和，最后一层的和就是答案。具体实现代码如下，请参考。

通过代码

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode() {} *     TreeNode(int val) { this.val = val; } *     TreeNode(int val, TreeNode left, TreeNode right) { *         this.val = val; *         this.left = left; *         this.right = right; *     } * } */class Solution {    public int deepestLeavesSum(TreeNode root) {        int ans = 0;        Queue<TreeNode> queue = new LinkedList<>();        queue.offer(root);        while (!queue.isEmpty()) {            ans = 0;            int size = queue.size();            for (int i = 0; i < size; i++) {                TreeNode node = queue.poll();                ans += node.val;                if (node.left != null) {                    queue.offer(node.left);                }                if (node.right != null) {                    queue.offer(node.right);                }            }        }        return ans;    }}