[LeetCode][1302. Deepest Leaves Sum] 2 Approaches: BFS(Level Order Travesal) and DFS(Get Max Depth, then Traversal)
By Long Luo
This article is the solution 2 Approaches: BFS(Level Order Travesal) and DFS(Get Max Depth, then Traversal) of Problem 1302. Deepest Leaves Sum.
Here shows 2 approaches to slove this problem: BFS(Level Order Travesal) and DFS(Get Max Depth, then Traversal).
BFS
To traverse the tree level by level, we generally use breadth first search. You can refer to this article Traverse the Tree Level by Level: Standard BFS Solution .1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37public int deepestLeavesSum(TreeNode root) {
if (root == null) {
return root.val;
}
int sum = 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int levelCount = queue.size();
boolean isDeepest = true;
sum = 0;
for (int i = 0; i < levelCount; i++) {
TreeNode curNode = queue.poll();
if (curNode.left == null && curNode.right == null) {
sum += curNode.val;
}
if (curNode.left != null) {
isDeepest = false;
queue.offer(curNode.left);
}
if (curNode.right != null) {
isDeepest = false;
queue.offer(curNode.right);
}
}
if (isDeepest && queue.isEmpty()) {
return sum;
}
}
return sum;
}
Analysis
- Time Complexity: \(O(n)\).
- Space Complexity: \(O(n)\).
DFS
- Traverse the tree to find the max depth.
- Traverse the tree again to compute the sum required.
1 | public int deepestLeavesSum_dfs(TreeNode root) { |
Analysis
- Time Complexity: \(O(n)\).
- Space Complexity: \(O(maxHeight)\).
All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)
Explore More Leetcode Solutions. 😉😃💗