LeetCode深度优先搜索：解决二叉树最深叶子节点求和问题

在 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 中存储的就是最深层叶子节点的和。