What is the main pattern to solve the Deepest Leaves Sum problem?

The problem is solved using binary-tree traversal and state tracking, specifically with either BFS or DFS to track depth and sum the deepest leaves.

How does Breadth-First Search help in solving this problem?

BFS helps by traversing the tree level by level, allowing us to easily identify the deepest level and sum the values of the leaves at that level.

What if the tree is unbalanced, how does it affect the solution?

The solution will still work for unbalanced trees as both BFS and DFS methods account for varying depths and leaf distributions.

Can we solve the problem using recursion?

Yes, DFS with recursion can track the current depth of the tree and sum the values of leaves at the deepest level.

What is the time complexity of solving the Deepest Leaves Sum problem?

The time complexity is O(n), where n is the number of nodes in the tree, since every node must be visited during traversal.

#1302

Medium

auto_awesome二分·树·traversal

LeetCode 题解工作台

层数最深叶子节点的和

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

树深度优先搜索广度优先搜索二叉树

题目描述

给你一棵二叉树的根节点 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⁴] 之间。
1 <= Node.val <= 100

lightbulb

解题思路

方法一：BFS

我们可以使用广度优先搜索，逐层遍历二叉树，并在遍历到每一层时计算该层的节点值之和。遍历完成后，返回最后一层的节点值之和。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是树中节点的数目。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def deepestLeavesSum(self, root: Optional[TreeNode]) -> int:
        q = deque([root])
        while q:
            ans = 0
            for _ in range(len(q)):
                node = q.popleft()
                ans += node.val
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Tests the candidate's understanding of tree traversal techniques.
question_mark
Evaluates problem-solving strategies related to tree depth and leaf-level summing.
question_mark
Looks for the candidate's ability to choose between BFS and DFS based on problem needs.

warning

常见陷阱

外企场景

error
Misunderstanding the problem’s requirement to only sum the deepest leaves.
error
Confusing the depth of the tree with the level of leaves.
error
Incorrectly handling the case when there is only one node in the tree.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Change the tree structure to allow non-binary trees and ask for the sum of deepest leaves.
arrow_right_alt
Ask for the sum of the deepest odd or even numbered leaves.
arrow_right_alt
Add extra constraints like calculating the sum at multiple levels, not just the deepest.

help

常见问题

外企场景

继续练习

#1315 祖父节点值为偶数的节点和 #1261 在受污染的二叉树中查找元素 #1361 验证二叉树