在 LeetCode 上探索二叉树问题常常会遇到挑战，特别是涉及到寻找最深层叶子节点的求和时。理解二叉树的结构以及如何有效地遍历它们是解决这类问题的关键。深度优先搜索（DFS）和广度优先搜索（BFS）是两种常用的树遍历算法，每种算法都有其独特的优势，可以应用于解决不同类型的二叉树问题。本文将深入探讨如何使用这两种算法来解决 LeetCode 1302：最深叶子节点求和 问题，并提供详细的代码示例和步骤说明。 最深叶子节点求和 问题的核心在于找到树的最深层，并将该层所有叶子节点的值加总。这不仅考察了对树结构的理解，还要求我们具备良好的算法设计能力。通过本文的学习，你将掌握使用 DFS 和 BFS 解决二叉树问题的实用技巧，提升算法能力，从而在 LeetCode 挑战中取得更好的成绩。掌握这些技能对于应对实际的软件开发场景也是非常有益的，可以帮助你更高效地解决复杂的数据结构问题。

关键点

理解二叉树的结构和术语（如根节点、叶子节点、深度）。

熟悉深度优先搜索 (DFS) 和广度优先搜索 (BFS) 两种树遍历算法。

掌握如何使用队列实现 BFS。

学习如何在 DFS 中使用递归方法。

了解如何有效地跟踪二叉树的深度。

能够编写清晰且可维护的代码来解决 LeetCode 二叉树问题。

能够分析算法的时间复杂度和空间复杂度。

二叉树和深度优先搜索 (DFS) 概述

什么是二叉树？

二叉树是一种常见的数据结构，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。树的顶部节点称为根节点，没有子节点的节点称为叶子节点。二叉树广泛应用于计算机科学领域，例如用于实现搜索树、堆和编译器设计等。

☞☞☞AI 智能聊天, 问答助手, AI 智能搜索, 免费无限量使用 DeepSeek R1 模型☜☜☜

以下是一些关于二叉树的重要术语：

• 根节点（Root Node）： 树的顶端节点，没有父节点。
• 叶子节点（Leaf Node）： 没有子节点的节点。
• 深度（Depth）： 从根节点到特定节点的路径长度。
• 高度（Height）： 从特定节点到其最远叶子节点的路径长度。
• 层（Level）： 根节点为第一层，其子节点为第二层，以此类推。

深度优先搜索（DFS）简介

深度优先搜索（DFS）是一种用于遍历或搜索树或图数据结构的算法。该算法从根节点开始，尽可能沿着每个分支深入搜索，直到到达叶子节点，然后回溯并探索其他分支。

DFS 可以通过递归或使用栈来实现。递归方法通常更简洁，但对于深度较大的树可能会导致栈溢出。使用栈的迭代方法可以避免栈溢出问题，但代码会相对复杂一些。

DFS 主要有三种遍历方式：

• 前序遍历（Preorder Traversal）： 先访问根节点，然后递归地前序遍历左子树和右子树。
• 中序遍历（Inorder Traversal）： 先递归地中序遍历左子树，然后访问根节点，最后递归地中序遍历右子树。
• 后序遍历（Postorder Traversal）： 先递归地后序遍历左子树和右子树，然后访问根节点。

选择哪种遍历方式取决于具体问题的需求。对于 最深叶子节点求和 问题，我们可以使用任何一种遍历方式，只要保证能够访问到所有叶子节点并计算它们的深度。

LeetCode 最深叶子节点求和问题分析

问题描述

LeetCode 1302：最深叶子节点求和 问题的描述如下：

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

示例：

输入：root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
输出：15

解释：

最深层叶子节点的层数是 3 。位于这一层的叶子节点是 7 和 8，所以返回 7 + 8 = 15 。

约束条件：

• 树中节点数目在范围 [1, 10^4] 之间。
• 每个节点的值在范围 [1, 100] 之间。

解题思路

解决 最深叶子节点求和 问题的关键在于找到二叉树的最深层，并将该层所有叶子节点的值加总。以下是使用深度优先搜索 (DFS) 的解题思路：

1. 初始化： 定义全局变量 maxDepth 用于存储最大深度，sum 用于存储最深层叶子节点的和。
2. DFS 遍历： 从根节点开始进行 DFS 遍历，同时记录当前节点的深度 depth。
3. 更新最大深度和求和：
   • 如果当前节点是叶子节点，且 depth 大于 maxDepth，则更新 maxDepth 为 depth，并将 sum 重置为当前节点的值。
   • 如果当前节点是叶子节点，且 depth 等于 maxDepth，则将当前节点的值加到 sum 中。
4. 递归遍历子树： 递归地遍历左子树和右子树，同时将 depth 加 1。
5. 返回结果： 遍历完成后，sum 中存储的就是最深层叶子节点的和。

DFS 代码示例 (C++)

以下是使用 C++ 实现的 DFS 代码示例：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int deepestLeavesSum(TreeNode* root) {
        int maxDepth = 0;
        int sum = 0;
        dfs(root, 1, maxDepth, sum);
        return sum;
    }

private:
    void dfs(TreeNode* node, int depth, int& maxDepth, int& sum) {
        if (!node) {
            return;
        }

        if (!node->left && !node->right) {
            if (depth > maxDepth) {
                maxDepth = depth;
                sum = node->val;
            } else if (depth == maxDepth) {
                sum += node->val;
            }
            return;
        }

        dfs(node->left, depth + 1, maxDepth, sum);
        dfs(node->right, depth + 1, maxDepth, sum);
    }
};

代码解释：

• deepestLeavesSum(TreeNode* root) 函数是主函数，用于计算最深层叶子节点的和。
• dfs(TreeNode* node, int depth, int& maxDepth, int& sum) 函数是递归函数，用于进行 DFS 遍历。
• 在 dfs 函数中，首先判断当前节点是否为空，如果为空则直接返回。
• 然后判断当前节点是否为叶子节点，如果是叶子节点，则根据其深度更新 maxDepth 和 sum。
• 最后递归地遍历左子树和右子树，同时将 depth 加 1。

如何运行 LeetCode 代码

在 LeetCode 平台提交代码

在 LeetCode 平台上运行代码非常简单。

1. 登录 LeetCode 账号： 首先，你需要登录你的 LeetCode 账号。如果你还没有账号，可以免费注册一个。
2. 找到问题： 在 LeetCode 题库中找到 最深叶子节点求和 问题。
3. 编写代码： 在代码编辑器中编写你的解决方案。你可以选择不同的编程语言，例如 C++、Java 或 Python。
4. 提交代码： 点击 提交 按钮，LeetCode 平台会自动编译并运行你的代码。平台会使用一系列测试用例来验证你的代码是否正确。
5. 查看结果： 提交后，你可以查看你的代码是否通过了所有测试用例。如果代码有错误，平台会提供详细的错误信息，帮助你进行调试。

在提交代码之前，建议先使用一些简单的测试用例来验证你的代码。这可以帮助你及早发现潜在的问题，提高代码的质量。

DFS 与 BFS 的优缺点比较

? Pros

DFS 具有更小的空间复杂度 (在平均情况下)。

BFS 可以保证找到最短路径 (如果问题需要)。

? Cons

DFS 可能会陷入无限循环 (需要额外的处理来避免)。

BFS 需要更大的内存来存储队列。

常见问题解答

如何优化 DFS 算法以避免栈溢出？

对于深度较大的树，递归实现的 DFS 可能会导致栈溢出。为了避免栈溢出，可以使用迭代方法来实现 DFS。迭代方法使用栈来模拟递归过程，从而避免了系统栈的限制。此外，还可以通过限制树的深度或使用其他算法（例如 BFS）来解决栈溢出问题。 class Solution { public: int deepestLeavesSum(TreeNode* root) { if (!root) { return 0; } int maxDepth = 0; int sum = 0; stack> st; st.push({root, 1}); while (!st.empty()) { TreeNode* node = st.top().first; int depth = st.top().second; st.pop(); if (!node->left && !node->right) { if (depth > maxDepth) { maxDepth = depth; sum = node->val; } else if (depth == maxDepth) { sum += node->val; } } else { if (node->right) { st.push({node->right, depth + 1}); } if (node->left) { st.push({node->left, depth + 1}); } } } return sum; } };

相关问题

如何使用广度优先搜索 (BFS) 解决最深叶子节点求和问题？

广度优先搜索 (BFS) 是一种从根节点开始逐层遍历树的算法。使用 BFS 解决 最深叶子节点求和 问题的步骤如下： 初始化： 使用一个队列来存储待访问的节点。将根节点加入队列。 逐层遍历： 从队列中取出节点，访问该节点，并将其子节点加入队列。 记录最深层叶子节点的和： 每次访问到叶子节点时，判断其深度是否为当前最大深度。如果是，则更新最大深度和最深层叶子节点的和。如果不是，则忽略该节点。 遍历完成： 当队列为空时，遍历完成。此时，最深层叶子节点的和就是所求的结果。 以下是使用 C++ 实现的 BFS 代码示例： class Solution { public: int deepestLeavesSum(TreeNode* root) { if (!root) { return 0; } queue q; q.push(root); int sum = 0; while (!q.empty()) { int size = q.size(); sum = 0; for (int i = 0; i left && !node->right) { sum += node->val; } else { if (node->left) { q.push(node->left); } if (node->right) { q.push(node->right); } } } } return sum; } }; 代码解释： deepestLeavesSum(TreeNode* root) 函数是主函数，用于计算最深层叶子节点的和。 使用一个队列 q 来存储待访问的节点。 在 while 循环中，每次遍历一层节点，并计算该层叶子节点的和。 当队列为空时，遍历完成。此时，sum 中存储的就是最深层叶子节点的和。

# python  # java  # node  # 计算机  # 编程语言  # 栈  # c++  # 递归函数  # 软件开发  # 常见问题 

相关栏目： 【 网站优化151355 】 【 网络推广146373 】 【 网络技术251813 】 【 AI营销90571 】

相关推荐： 如何在建站之星绑定自定义域名？  如何选择PHP开源工具快速搭建网站？  百度输入法ai组件怎么删除 百度输入法ai组件移除工具  详解ASP.NET 生成二维码实例（采用ThoughtWorks.QRCode和QrCode.Net两种方式）  今日头条微视频如何找选题 今日头条微视频找选题技巧【指南】  高性能网站服务器配置指南：安全稳定与高效建站核心方案  黑客如何利用漏洞与弱口令入侵网站服务器？  如何快速生成高效建站系统源代码？  香港代理服务器配置指南：高匿IP选择、跨境加速与SEO优化技巧  Laravel Artisan命令怎么自定义_创建自己的Laravel命令行工具完全指南  Swift中循环语句中的转移语句 break 和 continue  Laravel中间件如何使用_Laravel自定义中间件实现权限控制  浏览器如何快速切换搜索引擎_在地址栏使用不同搜索引擎【搜索】  Laravel如何集成Inertia.js与Vue/React？（安装配置）  如何在阿里云域名上完成建站全流程？  如何在 Pandas 中基于一列条件计算另一列的分组均值  如何在阿里云服务器自主搭建网站？  Win11应用商店下载慢怎么办 Win11更改DNS提速下载【修复】  Laravel怎么实现模型属性转换Casting_Laravel自动将JSON字段转为数组【技巧】  微信小程序制作网站有哪些,微信小程序需要做网站吗？  浅谈redis在项目中的应用  如何确认建站备案号应放置的具体位置？  如何正确选择百度移动适配建站域名？  JS中页面与页面之间超链接跳转中文乱码问题的解决办法  微信小程序 require机制详解及实例代码  Android仿QQ列表左滑删除操作  英语简历制作免费网站推荐,如何将简历翻译成英文？  如何在阿里云完成域名注册与建站？  如何在香港免费服务器上快速搭建网站？  今日头条AI怎样推荐抢票工具_今日头条AI抢票工具推荐算法与筛选【技巧】  JavaScript中的标签模板是什么_它如何扩展字符串功能  极客网站有哪些,DoNews、36氪、爱范儿、虎嗅、雷锋网、极客公园这些互联网媒体网站有什么差异？  javascript读取文本节点方法小结  EditPlus中的正则表达式实战(6)  Laravel怎么实现前端Toast弹窗提示_Laravel Session闪存数据Flash传递给前端【方法】  Laravel如何使用Service Container和依赖注入？（代码示例）  韩国服务器如何优化跨境访问实现高效连接？  Windows Hello人脸识别突然无法使用  如何彻底卸载建站之星软件？  Laravel如何集成第三方登录_Laravel Socialite实现微信QQ微博登录  如何为不同团队 ID 动态生成多个非值班状态按钮  浅述节点的创建及常见功能的实现  Laravel如何使用Guzzle调用外部接口_Laravel发起HTTP请求与JSON数据解析【详解】  HTML5空格在Angular项目里怎么处理_Angular中空格的渲染问题【详解】  如何用好域名打造高点击率的自主建站？  Win11怎么关闭资讯和兴趣_Windows11任务栏设置隐藏小组件  Laravel如何编写单元测试和功能测试？（PHPUnit示例）  如何在 Python 中将列表项按字母顺序编号（a.、b.、c. …）  如何用AWS免费套餐快速搭建高效网站？  网站建设整体流程解析，建站其实很容易！