Binary Tree Maximum Path Sum
A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.
The path sum of a path is the sum of the node’s values in the path.
root of a binary tree, return the maximum path sum of any path.
Input: root = [1,2,3]
Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.
Input: root = [-10,9,20,null,null,15,7]
Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.
- The number of nodes in the tree is in the range
[1, 3 * 104].
-1000 <= Node.val <= 1000
First of all, let’s simplify the problem and implement a function
max_gain(node) which takes a node as an argument and computes a maximum contribution that this node and one/zero of its subtrees could add.
In other words, it’s a maximum gain one could have including the node (and maybe one of its subtrees) into the path.
Hence if one would know for sure that the max path contains root, the problem would be solved as
max_gain(root). Unfortunately, the max path does not need to go through the root, and here is an example of such a tree.
That means one needs to modify the above function and to check at each step what is better: to continue the current path or to start a new path with the current node as the highest node in this new path.
Now everything is ready to write down an algorithm.
max_sumas the smallest possible integer and call
max_gain(node = root).
max_gain(node)with a check to continue the old path/to start a new path:
- Base case: if the node is null, the max gain is
max_gainrecursively for the node children to computing max gain from the left and right subtrees :
left_gain = max(max_gain(node.left), 0)and
right_gain = max(max_gain(node.right), 0).
- Now check to continue the old path or to start a new path. To start a new path would cost
price_newpath = node.val + left_gain + right_gain. Update
max_sumif it's better to start a new path.
- For the recursion return the max gain the node and one/zero of its subtrees could add to the current path :
node.val + max(left_gain, right_gain).
- Time complexity: O(N), where
Nis a number of nodes, since we visit each node not more than 2 times.
- Space complexity: O(H), where H is a tree height, to keep the recursion stack.