Binary Tree Maximum Path Sum

BinaryTreeMaximumPathSum.java

/**
 * Given a binary tree, find the maximum path sum.
 * The path may start and end at any node in the tree.
 * For example:
 * For example:
 *     1
      / \
     2   3
 * Return 6.
 */

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
 
public class Solution {
    public class MyInt {
        private int value;
        public MyInt(int val) {
            this.value = val;
        }
        public void set(int val) {
            this.value = val;
        }
        public int get() {
            return value;
        }
    }
    public int maxPathSum(TreeNode root) {
        MyInt maxSum = new MyInt(Integer.MIN_VALUE);
        findMaxSum(root, maxSum);
        return maxSum.get();
    }
    private int findMaxSum(TreeNode root, MyInt maxSum) {
        if(root == null)
            return 0;
        int cpath = 0;
        int left = findMaxSum(root.left, maxSum);
        int right = findMaxSum(root.right, maxSum);
        cpath = Math.max(root.val, Math.max(root.val + left, root.val + right));
        maxSum.set(Math.max(maxSum.get(), Math.max(root.val + left + right, cpath)));
        return cpath;
    }
}