DEV Community

loading...
Cover image for Solution: Deepest Leaves Sum

Solution: Deepest Leaves Sum

seanpgallivan
Fledgling software developer; the struggle is a Rational Approximation.
・4 min read

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.


Leetcode Problem #1302 (Medium): Deepest Leaves Sum


Description:


(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

Given the root of a binary tree, return the sum of values of its deepest leaves.


Examples:

Example 1:
Input: root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
Output: 15
Visual: Example 1 Visual
Example 2:
Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
Output: 19

Constraints:

  • The number of nodes in the tree is in the range [1, 104].
  • 1 <= Node.val <= 100

Idea:


(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

When asked to find information about a particular row of a binary tree, the normal thought is to use a breadth-first search (BFS) approach. A BFS approach usually involves the use of a queue data structure (q) so that we deal with the nodes of the tree in the proper order.

The trick is to deal with a single row at a time by making note of the length of the queue (qlen) when we start the row. Once we've processed that many nodes, we know we've just finished the current row and any remaining entries in q are from the next row. This can be accomplished easily with a nested loop.

In this case, processing a node simply means accumulating the running total (ans) for the row and then moving any children of the node onto the end of the queue.

When we start a new row, we can reset ans back to 0, and then just keep processing rows until q is empty. The last value of ans should be our final answer, so we should return ans.

Alternately, we can use a depth-first search (DFS) approach with recursion to traverse the binary tree. If we pass the row depth (lvl) as an argument to our recursive function (dfs), we can use it to update the values in an array of row sums (sums) by using lvl as an index (sums[lvl]). Then we can simply return the last value of sums as our answer.


Implementation:

There are only minor differences between the four languages.


Javascript Code:


(Jump to: Problem Description || Solution Idea)

w/ BFS:
var deepestLeavesSum = function(root) {
    let q = [root], ans, qlen, curr
    while (q.length) {
        qlen = q.length, ans = 0
        for (let i = 0; i < qlen; i++) {
            curr = q.shift(), ans += curr.val
            if (curr.left) q.push(curr.left)
            if (curr.right) q.push(curr.right)
        }
    }
    return ans
};
Enter fullscreen mode Exit fullscreen mode
w/ Recursive DFS:
var deepestLeavesSum = function(root) {
    let sums = []
    const dfs = (node, lvl) => {
        if (lvl === sums.length) sums[lvl] = node.val
        else sums[lvl] += node.val
        if (node.left) dfs(node.left, lvl+1)
        if (node.right) dfs(node.right, lvl+1)
    }
    dfs(root, 0)
    return sums[sums.length-1]
};
Enter fullscreen mode Exit fullscreen mode

Python Code:


(Jump to: Problem Description || Solution Idea)

w/ BFS:
class Solution:
    def deepestLeavesSum(self, root: TreeNode) -> int:
        q, ans, qlen, curr = [root], 0, 0, 0
        while len(q):
            qlen, ans = len(q), 0
            for _ in range(qlen):
                curr = q.pop(0)
                ans += curr.val
                if curr.left: q.append(curr.left)
                if curr.right: q.append(curr.right)
        return ans
Enter fullscreen mode Exit fullscreen mode
w/ Recursive DFS:
class Solution:
    def deepestLeavesSum(self, root: TreeNode) -> int:
        sums = []
        def dfs(node: TreeNode, lvl: int):
            if lvl == len(sums): sums.append(node.val)
            else: sums[lvl] += node.val
            if node.left: dfs(node.left, lvl+1)
            if node.right: dfs(node.right, lvl+1)
        dfs(root, 0)
        return sums[-1]
Enter fullscreen mode Exit fullscreen mode

Java Code:


(Jump to: Problem Description || Solution Idea)

w/ BFS:
class Solution {
    public int deepestLeavesSum(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        int ans = 0, qlen = 0;
        while (q.size() > 0) {
            qlen = q.size();
            ans = 0;
            for (int i = 0; i < qlen; i++) {
                TreeNode curr = q.poll();
                ans += curr.val;
                if (curr.left != null) q.add(curr.left);
                if (curr.right != null) q.add(curr.right);
            }
        }
        return ans;
    }
}
Enter fullscreen mode Exit fullscreen mode
w/ Recursive DFS:
class Solution {
    List<Integer> sums = new ArrayList<>();
    public int deepestLeavesSum(TreeNode root) {
        dfs(root, 0);
        return sums.get(sums.size()-1);
    }
    public void dfs(TreeNode node, int lvl) {
        if (lvl == sums.size()) sums.add(node.val);
        else sums.set(lvl, sums.get(lvl) + node.val);
        if (node.left != null) dfs(node.left, lvl+1);
        if (node.right != null) dfs(node.right, lvl+1);
    }
}
Enter fullscreen mode Exit fullscreen mode

C++ Code:


(Jump to: Problem Description || Solution Idea)

w/ BFS:
class Solution {
public:
    int deepestLeavesSum(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);
        int ans = 0, qlen = 0;
        while (q.size() > 0) {
            qlen = q.size(), ans = 0;
            for (int i = 0; i < qlen; i++) {
                TreeNode* curr = q.front(); q.pop();
                ans += curr->val;
                if (curr->left) q.push(curr->left);
                if (curr->right) q.push(curr->right);
            }
        }
        return ans;
    }
};
Enter fullscreen mode Exit fullscreen mode
w/ Recursive DFS:
class Solution {
public:
    vector<int> sums;
    int deepestLeavesSum(TreeNode* root) {
        dfs(root, 0);
        return sums.back();
    }
    void dfs(TreeNode* node, int lvl) {
        if (lvl == sums.size()) sums.push_back(node->val);
        else sums[lvl] += node->val;
        if (node->left) dfs(node->left, lvl+1);
        if (node->right) dfs(node->right, lvl+1);
    }
};
Enter fullscreen mode Exit fullscreen mode

Discussion (0)