124. Binary Tree Maximum Path Sum

Question

A 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 non-empty path.

Algorithm

• My first thought was to find the left, right and root.val, and solve it recursively. But I got stuck at the if the root is negative.
• So I draw some graph and try to identify all the possibilities of a sub tree. So I got left child value, right value, root value, left+root value, right + root value, left + right + root value. (This actually can be optimize, if the left is negative, we don't consider it as well as left+root value since all of them would be smaller than root value, same as right.)
• At this time I realized the result would appear in any place so I initiate a global max, to keep the max result we can get all the time.
• I wrote code version 1, and got error because I didn't handle the negative root and all the null node I return 0, then the null node value is lager than the real node value which is not right.
• So I wrote version 2, which handles both positive and negative root value. This time the code isn't all good.
• For the case [9,6,-3,null,null,-6,2,null,null,2,null,-6,-6,-6], the path don't reach the leaf node and stop in the middle somewhere. So in the walk through I realized that the return value should be the max among left+root, right+root or the root itself(we are aiming to get the max in that sub path.)
• So the final code would be the following it's accepted but it's unreadable. The pseudo code is like :

helper(TreeNode root) {
    left, right, leftroot, rightroot, rootval, leftrightroot;
    max = max(left, right, leftroot, rightroot, rootval, leftrightroot);
    return max(leftroot, rightroot, root);
}

Code

/**
 * 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 = -2000;
    public int maxPathSum(TreeNode root) {
        helper(root);
        return max;
    }
    
    private int helper(TreeNode root) {
        // if (root == null) return 0;
        int left, right;
        if (root.val >= 0) {
            left = root.left == null ? 0 : helper(root.left);
        } else {
            left = root.left == null ? -2000 : helper(root.left);
        }
        // int left = helper(root.left);
        // int right = helper(root.right);
        if (root.val >= 0) {
            right = root.right == null ? 0 : helper(root.right);
        } else {
            right = root.right == null ? -2000 : helper(root.right);
        }
        int leftRoot = root.val + left;
        int rightRoot = root.val + right;
        
        max = Math.max(Math.max(Math.max(root.val, Math.max(leftRoot, rightRoot)), Math.max(left + right + root.val, Math.max(left, right))), max);
        return Math.max(Math.max(leftRoot, rightRoot), root.val);
    }
}

Code2

This is the reference answer or standard solution to the problem. It didn't think too much on left, right, leftroot, rightroot, rootval, leftrightroot; these things.

The logic behind is simple, just like I said in the algorithm, we only focus on if the sub path result is positive, otherwise it's 0 and useless(cannot contribute to a larger path sum).

Rest logic is similar, max all the time, return max for left, right or root.(in this code, due to the left or right is abandoned if they are negative, the final return Math.max(left, right) + root.val is returning solely the root value).

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