20. Maximum path sum

In a binary tree, a path is a list of nodes where there is an edge between every pair of neighbouring nodes. A node may only make a single appearance in the sequence.

The total of each node's values along a path is its path sum. Return the largest path sum of all non-empty paths given the root of a binary tree.

Note: The path does not have to go via the root.

Example 1:

Input : root = [20, 9, -10, null, null, 15, 7]

Output : 34

Explanation : The path from node 15 to node 9 has maximum path sum.

The path is 15 -> -10 -> 20 -> 9.

Example 2:

Input : root = [-10, 9, 20, null, null, 15, 7]

Output : 42

Explanation : The path from node 15 to node 7 has maximum path sum.

The path is 15 -> 20 -> 7.

Now Your Turn!

Pick the correct output for the given input

Input : root = [1, 2, 3, null, 4]

Still unsure what the problem is asking ?

Let’s go through a few more examples, step by step, to make it clearer.

Constraints:

  • 1 <= Number of Nodes <= 3*104
  • -103 <= Node.val <= 103

Hints

Frequently Occurring Doubts

Interview Follow-up Questions

Fun Facts

0
/**
* Definition for a binary tree node.
* struct TreeNode {
* int data;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int val) : data(val) , left(nullptr) , right(nullptr) {}
* };
**/
 
class Solution {
public:
int maxPathSum(TreeNode* root) {
//your code goes here
}
};
Test Case

Input:

Root
to save your code