Binary Tree Maximum Path Sum

class Solution {
public:
   int maxPathSum(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int csum;
        int maxsum = INT_MIN;
        maxPathSumHelper(root, csum, maxsum);
        return maxsum;

    }
    void maxPathSumHelper(TreeNode *node, int &csum, int &maxsum) {
        if (!node) {
            csum = 0;
            return;
        }
        int lsum = 0, rsum = 0;
        maxPathSumHelper(node->left, lsum, maxsum);
        maxPathSumHelper(node->right, rsum, maxsum);
        csum = max(node->val, max(node->val + lsum, node->val + rsum));
        maxsum = max(maxsum, max(csum, node->val + lsum + rsum));
    }
};

One needs to handle three cases:

1. Left tree path plus the current root.
2. Right tree path plus the current root.
3. The path passes through the root and hence one needs to consider the left path + current root + right path.

In addition compare with the max path so far and update accordingly.

Java doesn't allow to modify passed-in parameters. For this problem, we need to keep track two things during recursions: the max subpath sum and the current max sum for a given node. One way is to let the helper method return an array of two items, as shown in @Andy's solution; Another way is to pass in the current max as an array of one item.

public static int maxPathSum(TreeNode root) {
    // pass the curmanx in an array that contains only one value
    ArrayList<Integer> curMax = new ArrayList<Integer>(1);
    curMax.add(Integer.MIN_VALUE);
    maxSubPath(root, curMax);
    return curMax.get(0);
}

private static int maxSubPath(TreeNode root, ArrayList<Integer> curMax) {
    if (root == null)  return 0;
    int leftMax = Math.max(0, maxSubPath(root.left, curMax));
    int rightMax = Math.max(0, maxSubPath(root.right, curMax));
    curMax.set(0, Math.max(curMax.get(0), root.val+leftMax+rightMax));
    return Math.max(root.val+leftMax, root.val+rightMax);
}

class Solution {
    public:
        int maxPathSum(const TreeNode * root) {
            int g2root;
            return maxPathSumImp(root, g2root);
        }

        int maxPathSumImp(const TreeNode * r, int & g2root) {
            if (!r) {
                g2root = 0;
                return INT_MIN;
            }
            int g2l, g2r;
            int maxl = maxPathSumImp(r->left,  g2l);
            int maxr = maxPathSumImp(r->right, g2r);

            g2root = r->val + std::max(0, std::max(g2l, g2r));
            int g  = r->val + std::max(g2l, 0) + std::max(g2r, 0);
            return std::max(std::max(maxl, maxr), g);
        }
};

class Maxes{
public:
    int tmax;//max of terminated in self
    int pmax;//max of pass self
    int nmax;//max of non-relative to self
    Maxes() {tmax = pmax = 0; nmax = (1 << (sizeof(int) * 8 - 1));}
    inline int getMax() {
        int m = tmax;
        if(m < pmax) m = pmax;
        if(m < nmax) m = nmax;
        return m;
    }
};
class Solution {
public:
    Maxes maxPath(TreeNode *root) {
        Maxes m;
        if(NULL == root)
            return m;

        Maxes l = maxPath(root->left);
        Maxes r = maxPath(root->right);

        //tmax is the max value which terminated at this node
        //when all of it's children is negative, this is it's value
        //or add the max value terminated at it's children
        m.tmax = max(l.tmax,r.tmax);
        if(m.tmax < 0) m.tmax = 0;
        m.tmax += root->val;

        //pmax is the max value which is pass this node
        //that is it's value terminated at it's children (if have, or zero), add self value
        m.pmax = l.tmax + r.tmax + root->val;

        //nmax is the max value which not including current node
        if(root->left)
            m.nmax = l.getMax();
        if(root->right) {
            int rmax = r.getMax();
            if(m.nmax < rmax) m.nmax = rmax;
        }
        return m;
    }
    int maxPathSum(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        Maxes m = maxPath(root);
        int ma = m.getMax();
        return ma;
    }
};

public class Solution {

    public int maxPathSum(TreeNode root) {
        int[] r = helper(root);
        return r[1];
    }

    private int[] helper(TreeNode node) {
        if (node == null)
            return new int[]{0, Integer.MIN_VALUE};

        int[] left = helper(node.left);
        int[] right = helper(node.right);

        int[] r = new int[2];
        r[0] = Math.max(node.val, Math.max(node.val+left[0], node.val+right[0]));

        r[1] = Math.max(Math.max(r[0], Math.max(left[1], right[1])), left[0] + right[0] + node.val);
        return r;
    }

}

• Java is pass by value. So passing the value of a reference and modifying its content in the callee instead of passing the integer value itself.

.

public int maxPathSum(TreeNode root) {
    ArrayList<Integer> maxSum = new ArrayList<Integer>(1);
    maxSum.add(Integer.MIN_VALUE);
    getMaxSum(root,maxSum);
    return maxSum.get(0);
}

public int getMaxSum(TreeNode root,ArrayList<Integer> maxSum){
    if(root==null){
        return 0;
    }

    int leftSum=0,rightSum=0;
    leftSum = getMaxSum(root.left,maxSum);
    rightSum = getMaxSum(root.right,maxSum);

    int curSum = Math.max(root.val,Math.max(root.val+leftSum,root.val+rightSum));
    maxSum.add(0,Math.max(maxSum.get(0), Math.max(curSum,root.val+leftSum+rightSum)));
    return curSum;
}