_1302. Deepest Leaves Sum.md

1302. Deepest Leaves Sum

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : June 07, 2024

Last updated : July 09, 2024

---

Related Topics : Tree, Depth-First Search, Breadth-First Search, Binary Tree

Acceptance Rate : 86.36 %

---

Solutions

• m1302 v2 2 pass traversal much faster.c
• m1302.c
• m1302.js
• m1302.py

C

m1302 v2 2 pass traversal much faster.c

// Not that efficient :l
// probs cause of all the mallocing

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int max(int a, int b) {
    return (a > b) ? a : b;
}

int findDepth(struct TreeNode* current) {
    if (!current) 
        return 0;
    return 1 + max(findDepth(current->left), findDepth(current->right));
}

int sumDeepest(struct TreeNode* current, int targetDepth, int currDepth) {
    if (!current)
        return 0;
    if (currDepth == targetDepth)
        return current->val;
    
    return sumDeepest(current->left, targetDepth, currDepth + 1) + 
           sumDeepest(current->right, targetDepth, currDepth + 1);
}

int deepestLeavesSum(struct TreeNode* root) {
    return sumDeepest(root, findDepth(root), 1);
}

m1302.c

// Not that efficient :l
// probs cause of all the mallocing

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

int* helper(struct TreeNode* current) {
    if (!current->left && !current->right) {
        int* output = (int*) malloc(sizeof(int) * 2);
        output[0] = current->val;
        output[1] = 1;
        return output;
    }

    if (!current->left) {
        int* right = helper(current->right);
        right[1] += 1;
        return right;
    }

    if (!current->right) {
        int* left = helper(current->left);
        left[1] += 1;
        return left;
    }

    int* left = helper(current->left);
    int* right = helper(current->right);

    if (left[1] == right[1]) {
        left[0] += right[0];
        left[1] += 1;
        free(right);
        return left;
    } else if (left[1] > right[1]) {
        free(right);
        left[1] += 1;
        return left;
    } else {
        free(left);
        right[1] += 1;
        return right;
    }
}

int deepestLeavesSum(struct TreeNode* root) {
    int* output = helper(root);
    int out = output[0];
    free(output);
    return out;
}

JavaScript

m1302.js

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var deepestLeavesSum = function(root) {
    var deepestDepth = 0;
    var output = 0;
    
    function dfs(curr, currDepth) {
        if (curr == undefined) {
            return;
        }
        if (currDepth > deepestDepth) {
            deepestDepth = currDepth;
            output = 0;
        }
        if (currDepth == deepestDepth) {
            output += curr.val;
        }
        currDepth++;
        dfs(curr.left, currDepth)
        dfs(curr.right, currDepth)
    }
    dfs(root, 0);
    return output;
};

Python

m1302.py

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def deepestLeavesSum(self, root: Optional[TreeNode]) -> int:
        def helper(curr: Optional[TreeNode]) -> (int, int) : # (sum, height)
            if not curr.left and not curr.right:
                return (curr.val, 1)
            if not curr.left :
                right = helper(curr.right)
                return (right[0], right[1] + 1)
            if not curr.right :
                left = helper(curr.left)
                return (left[0], left[1] + 1)

            left = helper(curr.left)
            right = helper(curr.right)

            if left[1] == right[1] :
                return (left[0] + right[0], left[1] + 1)
            if left[1] > right[1] :
                return (left[0], left[1] + 1)
            return (right[0], right[1] + 1)

        return helper(root)[0]