1302 Deepest Leaves Sum¶

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

Example 1:

alt

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

Solution 1: Recursion¶

Time complexity: \(O(n)\) Space complexity: \(O(n)\)

class Solution {
public:
  int deepestLeavesSum(TreeNode* root) {
    int sum = 0;
    int max_depth = 0;
    function<void(TreeNode*, int)> dfs = [&](TreeNode* n, int d) {
      if (!n) return;
      if (d > max_depth) {
        max_depth = d;
        sum = 0;
      }
      if (d == max_depth) sum += n->val;
      dfs(n->left, d + 1);
      dfs(n->right, d + 1);
    };
    dfs(root, 0);
    return sum;
  }
};