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.
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). 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)
Space Complexity O(n)
TreeNode.of
function can be used to create an entire binary tree using 1 line of code. The input is a BFS traversal of the tree including nulls, and the output is the root node of the tree.TreeNode.of([1, None, 2, None, 3])
ListNode.of
function lets you create an entire Linked List using 1 line of code. The input is an array, and the output is the head of the Linked List.ListNode.of([1, 2, 3])
ListNode.of([1, 2, 3], 1)
GraphNode.of
function lets you create an entire Graph using 1 line of code. The input is an Adjacency Matrix, and the output is the first node in the matrix.GraphNode.of([ ['A', 1, 2], ['B', 2], ['C', 0] ])
[['__init__', 15], ['add', 16], ['get']]
c = MyClass(15) c.add(16) c.get()
TreeNode.of
function can be used to create an entire binary tree using 1 line of code. The input is a BFS traversal of the tree including nulls, and the output is the root node of the tree.TreeNode.of([1, None, 2, None, 3])
ListNode.of
function lets you create an entire Linked List using 1 line of code. The input is an array, and the output is the head of the Linked List.ListNode.of([1, 2, 3])
ListNode.of([1, 2, 3], 1)
GraphNode.of
function lets you create an entire Graph using 1 line of code. The input is an Adjacency Matrix, and the output is the first node in the matrix.GraphNode.of([ ['A', 1, 2], ['B', 2], ['C', 0] ])
[['__init__', 15], ['add', 16], ['get']]
c = MyClass(15) c.add(16) c.get()