1302. Deepest Leaves Sum

1302. Deepest Leaves Sum

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

My Solutions:

deepest leaves sum的意思是，最深的node的总和，在例子1里，指7+8。Traverse the tree to find the max depth. Traverse the tree again to compute the sum required.

/**
 * 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;
 *     }
 * }
 */
class Solution {
    public int deepestLeavesSum(TreeNode root) {
        int height = maxDepth(root);
        return sumOfNodesAtHeight(root, height - 1); // 这里需要用height-1, 因为height代表所有node的层数，在计算height时，最深的node的height是1。但是在找到最深的node时，我们需要它的height=0。
    }
    
    private int sumOfNodesAtHeight(TreeNode root, int height) {
        if (root == null) return 0;
        if (height == 0) return root.val;
        return sumOfNodesAtHeight(root.left, height - 1) + sumOfNodesAtHeight(root.right, height - 1);
    }
    
    private int maxDepth(TreeNode root) {
        if (root == null) return 0;
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}