Medium

题目描述

给你一棵二叉树的根节点 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

提示：

  • 树中节点数目在范围 [1, 10^4] 之内
  • 1 <= Node.val <= 100

解题思路

这道题要求找到二叉树中最深叶节点的和。我们可以用多种方法来解决：

方法一：层序遍历（BFS） 使用队列进行层序遍历，记录每一层的节点值之和。遍历完所有层后，最后一层的和就是最深叶节点的和。这种方法思路简单直观。

方法二：深度优先搜索（DFS） 先通过一次 DFS 找到树的最大深度，然后再通过一次 DFS 遍历，将深度等于最大深度的节点值累加起来。

方法三：一次 DFS（推荐） 在递归过程中同时记录当前深度和当前深度下的节点值之和。如果发现更深的层次，就更新最大深度并重置和；如果是相同深度，就累加到当前和中。这种方法只需要一次遍历，效率最高。

本题的关键是准确识别最深的层次，然后对该层次的所有叶节点求和。层序遍历方法最容易理解，而一次 DFS 的方法效率最优。

代码实现

class Solution {
public:
    int deepestLeavesSum(TreeNode* root) {
        int maxDepth = 0;
        int sum = 0;
        
        function<void(TreeNode*, int)> dfs = [&](TreeNode* node, int depth) {
            if (!node) return;
            
            if (depth > maxDepth) {
                maxDepth = depth;
                sum = node->val;
            } else if (depth == maxDepth) {
                sum += node->val;
            }
            
            dfs(node->left, depth + 1);
            dfs(node->right, depth + 1);
        };
        
        dfs(root, 0);
        return sum;
    }
};

class Solution:
    def deepestLeavesSum(self, root: Optional[TreeNode]) -> int:
        max_depth = 0
        total_sum = 0
        
        def dfs(node, depth):
            nonlocal max_depth, total_sum
            if not node:
                return
            
            if depth > max_depth:
                max_depth = depth
                total_sum = node.val
            elif depth == max_depth:
                total_sum += node.val
            
            dfs(node.left, depth + 1)
            dfs(node.right, depth + 1)
        
        dfs(root, 0)
        return total_sum

public class Solution {
    public int DeepestLeavesSum(TreeNode root) {
        int maxDepth = 0;
        int sum = 0;
        
        void Dfs(TreeNode node, int depth) {
            if (node == null) return;
            
            if (depth > maxDepth) {
                maxDepth = depth;
                sum = node.val;
            } else if (depth == maxDepth) {
                sum += node.val;
            }
            
            Dfs(node.left, depth + 1);
            Dfs(node.right, depth + 1);
        }
        
        Dfs(root, 0);
        return sum;
    }
}

var deepestLeavesSum = function(root) {
    if (!root) return 0;
    
    let queue = [root];
    let sum = 0;
    
    while (queue.length > 0) {
        let levelSize = queue.length;
        sum = 0;
        
        for (let i = 0; i < levelSize; i++) {
            let node = queue.shift();
            sum += node.val;
            
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
    }
    
    return sum;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

算法时间复杂度空间复杂度
DFS一次遍历O(n)O(h)
BFS层序遍历O(n)O(w)

其中 n 是树中节点的数量，h 是树的高度，w 是树的最大宽度。对于 DFS 方法，空间复杂度主要来自递归栈；对于 BFS 方法，空间复杂度主要来自队列存储。