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: , , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s