public int calMaxPathSum(TreeNode root, int sum) {
        if (root == null) return sum;

        int leftSum = calMaxPathSum(root.left, sum);
        int rightSum = calMaxPathSum(root.right, sum);

        if (sum < 0)
            sum = root.val;

        int maxSumWithCurNode = root.val;

        if (rightSum > 0)
            maxSumWithCurNode += rightSum;

        if (leftSum > 0)
            maxSumWithCurNode += leftSum;


        if (leftSum > rightSum && leftSum > 0)
            sum += leftSum;
        else if (leftSum <= rightSum && rightSum > 0)
            sum += rightSum;

        if (maxSumWithCurNode > max)
            max = maxSumWithCurNode;

        return sum;
    }