Deepest Leaves Sum

This approach involves two separate traversals of the tree. The first traversal is to determine the maximum depth of the tree. The second traversal then sums up the values of all nodes that are at this maximum depth.

• First Pass: Find Maximum Depth
  • Define a recursive function findMaxDepth(node).
  • The base case is a null node, which has a depth of 0.
  • For a non-null node, the depth is 1 + max(findMaxDepth(node.left), findMaxDepth(node.right)).
  • Call this on the root to find the maxDepth of the entire tree.
• Second Pass: Sum at Maximum Depth
  • Define a second recursive function sumAtDepth(node, currentDepth, maxDepth).
  • Initialize a sum variable to 0.
  • Traverse the tree, passing the currentDepth.
  • If currentDepth equals maxDepth, add the node's value to the sum.
  • Recursively call for left and right children with currentDepth + 1.
• Return the final sum.

This method breaks the problem down into two simpler, sequential steps.

1. First Pass - Find Maximum Depth: We first need to know what the 'deepest' level is. We can find this by performing a standard DFS traversal. A recursive function findMaxDepth(node) can compute the height of the subtree rooted at node. The height of a null node is 0, and the height of a non-null node is 1 plus the maximum height of its left and right subtrees. By calling this on the root, we get the maximum depth of the entire tree.

2. Second Pass - Sum Deepest Leaves: Once we have the maxDepth, we traverse the tree again. This time, we use another recursive function, say sumAtDepth(node, currentDepth, maxDepth). We pass down the current depth of each node. If a node's currentDepth matches the maxDepth we found earlier, we add its value to a running total. After this second traversal is complete, the total will be our answer.

class Solution {
    int sum = 0;

    public int deepestLeavesSum(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int maxDepth = findMaxDepth(root);
        sumAtDepth(root, 1, maxDepth);
        return sum;
    }

    private int findMaxDepth(TreeNode node) {
        if (node == null) {
            return 0;
        }
        return 1 + Math.max(findMaxDepth(node.left), findMaxDepth(node.right));
    }

    private void sumAtDepth(TreeNode node, int currentDepth, int maxDepth) {
        if (node == null) {
            return;
        }
        if (currentDepth == maxDepth) {
            sum += node.val;
        }
        sumAtDepth(node.left, currentDepth + 1, maxDepth);
        sumAtDepth(node.right, currentDepth + 1, maxDepth);
    }
}