1302. Deepest Leaves Sum
Description
Given the root of a binary tree, return the sum of values of its deepest leaves.
Constraints
The number of nodes in the tree is in the range
[1, 104].1 <= Node.val <= 100
Approach
Links
GeeksforGeeks
ProgramCreek
YouTube
Examples
Input: root = [1, 2, 3, 4, 5, null, 6, 7, null, null, null, null, 8]
Output: 15
Input: root = [6, 7, 8, 2, 7, 1, 3, 9, null, 1, 4, null, null, null, 5]
Output: 19
Solutions
// Definition for a binary tree node.
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}/**
* Time complexity :
* Space complexity :
*/
class Solution {
private int maxDepth = 0;
private Map<Integer, Integer> leavesSum = new HashMap();
public int deepestLeavesSum(TreeNode root) {
if(root == null) {
return 0;
}
deepestLeavesSum(root, maxDepth);
return leavesSum.get(maxDepth);
}
private void deepestLeavesSum(TreeNode node, int depth) {
if(node == null) {
return;
}
if(node.left == null && node.right == null) {
int sum = leavesSum.getOrDefault(depth, 0) + node.val;
leavesSum.put(depth, sum);
maxDepth = Math.max(maxDepth, depth);
return;
}
deepestLeavesSum(node.left, depth+1);
deepestLeavesSum(node.right, depth+1);
}
}/**
* Time complexity :
* Space complexity :
*/
class Solution {
private List<Integer> leavesSum = new ArrayList();
public int deepestLeavesSum(TreeNode root) {
if(root == null) {
return 0;
}
deepestLeavesSum(root, 0);
return leavesSum.get(leavesSum.size()-1);
}
private void deepestLeavesSum(TreeNode node, int depth) {
if(node == null) {
return;
}
if(leavesSum.size() <= depth) {
leavesSum.add(0);
}
if(node.left == null && node.right == null) {
int sum = leavesSum.get(depth) + node.val;
leavesSum.set(depth, sum);
return;
}
deepestLeavesSum(node.left, depth+1);
deepestLeavesSum(node.right, depth+1);
}
}Follow up
Last updated
Was this helpful?