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

Examples

Input: [1, 2, 3]

Output: 6

Explanation:

Solutions

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

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

Previous123. Best Time to Buy and Sell Stock III Next125. Valid Palindrome

Last updated 5 years ago

Was this helpful?