This content originally appeared on DEV Community and was authored by seanpgallivan
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
rootof 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 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
};
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]
};
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
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]
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;
}
}
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);
}
}
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;
}
};
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);
}
};
This content originally appeared on DEV Community and was authored by seanpgallivan
seanpgallivan | Sciencx (2021-04-11T08:28:44+00:00) Solution: Deepest Leaves Sum. Retrieved from https://www.scien.cx/2021/04/11/solution-deepest-leaves-sum/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.