[LeetCode][1302. Deepest Leaves Sum] 2 Approaches: BFS(Level Order Travesal) and DFS(Get Max Depth, then Traversal)

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 2k 阅读时长 ≈ 2 分钟

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
37
public 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

  1. Traverse the tree to find the max depth.
  2. Traverse the tree again to compute the sum required.
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
public int deepestLeavesSum_dfs(TreeNode root) {
    int maxDepth = getMaxDepth(root);
    return dfs(root, 1, maxDepth);
}

public int getMaxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }

    return Math.max(getMaxDepth(root.left), getMaxDepth(root.right)) + 1;
}

public int dfs(TreeNode root, int curDepth, int maxDepth) {
    if (root == null) {
        return 0;
    }

    if (curDepth == maxDepth) {
        return root.val;
    }

    int left = dfs(root.left, curDepth + 1, maxDepth);
    int right = dfs(root.right, curDepth + 1, maxDepth);

    return left + right;
}

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. 😉😃💗