# Binary Tree Maximum Path Sum

Hard

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. Given the `root` of a binary tree, return the maximum path sum of any path.

``````Input: root = [-10,9,20,null,null,15,7]
Output: 42
Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.
``````

Constraints:

• The number of nodes in the tree is in the range `[1, 3 * 104]`.
• `-1000 <= Node.val <= 1000`
```/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode() {}
*     TreeNode(int val) { this.val = val; }
*     TreeNode(int val, TreeNode left, TreeNode right) {
*         this.val = val;
*         this.left = left;
*         this.right = right;
*     }
* }
*/
class Solution {

int max_sum = Integer.MIN_VALUE;

public int maxPathSum(TreeNode root) {
if(root == null){
return 0;
}
calculateMaximumPathSum(root);
return max_sum;
}

private int calculateMaximumPathSum(TreeNode node){
if(node == null){
return 0;
}
int left_sum = Math.max(calculateMaximumPathSum(node.left), 0);
int right_sum = Math.max(calculateMaximumPathSum(node.right), 0);
int cur_sum = node.val + left_sum + right_sum;
max_sum = Math.max(cur_sum, max_sum);
return Math.max(left_sum, right_sum) + node.val;
}
}
```

Complexity Analysis

• Time Complexity: `O(N)`, where `N` is 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. In the average case of balanced tree, the tree height `H=logN`, in the worst case of skewed tree, `H = N`.

Categories: Binary Tree

Tagged as: , , ,