Binary Tree Maximum Path Sum II

Given a binary tree, find the maximum path sum from root.

The path may end at any node in the tree and contain at least one node in it.

Solution:

Similar to Maximum Depth of Binary Tree with three modification:

• Add value of the node instead of 1 (for current height in Maximum Depth of Binary Tree)
• If the sum of subtree is negative, we prefer not selecting it
• When node is null, return Integer.MIN_VALUE

This is a simple version of Binary Tree Maximum Path Sum.

Code:

public class Solution {

    public int maxPathSum2(TreeNode root) {
        if (root == null) {
            return Integer.MIN_VALUE;
        }
        int left2any = Math.max(maxPathSum2(root.left), 0);
        int right2any = Math.max(maxPathSum2(root.right), 0);
        return Math.max(left2any, right2any) + root.val;
    }
}