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

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: root = [1, 2, 3, 4, 5, null, 6, 7, null, null, null, null, 8]

Output: 15

Example 2

Input: root = [6, 7, 8, 2, 7, 1, 3, 9, null, 1, 4, null, null, null, 5]

Output: 19

Solutions

TreeNode

// 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;
	}
}

Solution 1

/**
 * 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);
    }
}

Solution 2

/**
 * 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