My Leetcode: Binary Tree Maximum Path Sum (Java)

Preorderly traverse the whole tree. For each  node calculate Max(root, root+leftSide, root+rightSide, leftSide+root+rightSide ), update max[0] (which is used to store max value), then return Max (root+leftSide, root+rightSide, root)

    public int maxPathSum(TreeNode root) {

        if (root==null){

            return 0;

        }

        int[]  max={Integer.MIN_VALUE};

        maxPathSum(root, max);

        return max[0];

    

    }

    private int maxPathSum(TreeNode root, int[] max ){

        if (root==null){

            return 0;

        }

       max[0]=Math.max(max[0], root.val);

        

       int leftMax=maxPathSum(root.left, max)+root.val;

       max[0]=Math.max(leftMax, max[0]);

       

       int rightMax=maxPathSum(root.right, max)+root.val;

        max[0]=Math.max(rightMax, max[0]);

           public int maxPathSum(TreeNode root) {

        if (root==null){

            return 0;

        }

        int[]  max={Integer.MIN_VALUE};

        maxPathSum(root, max);

        return max[0];

    

    }

    private int maxPathSum(TreeNode root, int[] max ){

        if (root==null){

            return 0;

        }

       max[0]=Math.max(max[0], root.val);

        

       int leftMax=maxPathSum(root.left, max)+root.val;

       max[0]=Math.max(leftMax, max[0]);

       

       int rightMax=maxPathSum(root.right, max)+root.val;

        max[0]=Math.max(rightMax, max[0]);

        max[0]=Math.max(rightMax+leftMax-root.val, max[0]);

       return Math.max(Math.max(leftMax, rightMax), root.val);

    }


        max[0]=Math.max(rightMax+leftMax-root.val, max[0]);

       return Math.max(Math.max(leftMax, rightMax), root.val);

    }

Also refer to http://blog.csdn.net/fightforyourdream/article/details/16894069
Read full article from My Leetcode: Binary Tree Maximum Path Sum (Java)