Recursion

Max Node to Leaf Sum

You're given the root node of a binary tree root. Set the value of each node in the tree equal to the largest sum from that node to a leaf node (the "Maximum Node-to-Leaf Sum").

A "leaf node" is defined as a node with no children.

Example 1:

Explanation: The maximum sum from the root node to a leaf node is 1+3 = 4.

Example 2:

Explanation: The maximum sum from the root node to a leaf is 1+(-1)+8. The max sum from the left node is -1+8. The max sum from the right node is 1+2.

First Few Test Cases:

0. Problem

We want to set each node's value to the largest path sum going down to any leaf. To do that, we first have to compute the largest sum to any leaf. We'll write a function that computes the sum, and then we'll hijack that function to set the value.

1. Recursion

The maximum sum down from a node to a leaf must include the node's value. It either goes down through the left node or the right node, whichever sum is bigger. Here's the recursion:

2. Base case

One base case is that the recursion should stop when it reaches a leaf node. The value of maxSum in this case is node.val, since the maxSum down to a leaf, at a leaf, is just the leaf node's value.

The recursion might also reach a null node too - this happens when a node only has 1 child. There's no way to get to a leaf node from a null node, so so it doesn't make sense to have maxSum(null)\small \text{maxSum(null)}. We'll set it equal to -infinity so it gets ignored.

3. Code

We can code up the maxSum function by just combining recursion and base case. Since it's a recursive function, it will visit every node in the tree. So we'll hijack the function to set every node's value, too. We'll do this on the last line so it's the last thing that happens to each node, so we won't be changing values under our own feet.

Time Complexity O(n)O(n)

Space Complexity O(n)O(n)

Mark as Completed:
Submits:
maximumLeafSum
Imports:
TreeNode
Test your code to get an output here!
maximumLeafSum(
)
Test your code to get an output here!