124. Binary Tree Maximum Path Sum

Description

Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Constraints

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: [1, 2, 3]

Output: 6

Explanation:

Example 2

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

Output: 42

Explanation:

Solutions

TreeNode

// 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;
    }
}

Solution 1

/**
 * 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.
 */

class Solution {
    private int maxSum = Integer.MIN_VALUE;
    
    public int maxPathSum(TreeNode root) {
        helper(root);
        return maxSum;
    }
    
    private int helper(TreeNode node) {
        if(node == null) return 0;
        
        int leftSum = Math.max(helper(node.left), 0);
        int rightSum = Math.max(helper(node.right), 0);
        
        int sum = leftSum + node.val + rightSum;
        
        maxSum = Math.max(maxSum, sum);
        
        return node.val + Math.max(leftSum, rightSum);
    }
}

Follow up