Deepest Leaves Sum - Easy DFS solution

Binary Tree     Breadth-First Search     Depth-First Search     Medium     Tree    

Problem Statement:

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

 

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

 

Constraints:

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

Solution:

class Solution {
public:
    int height(TreeNode *root)
    {
        if (!root) return 0;
        return 1+max(height(root->left),height(root->right));
    }
    void util(TreeNode *root, int h, int &res)
    {
        if (!root) return;
        if (h==0) res+=root->val;
        util(root->left, h-1, res);
        util(root->right, h-1, res);
    }
    int deepestLeavesSum(TreeNode* root) {
        int H = height(root);
        int res=0;
        util(root, H-1, res);
        return res;
    }
};