LeetCode 124: Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.
The path may start and end at any node in the tree.
For example:
Given the below binary tree,

       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 {
	// Store maximum path sum
	private int max; 
	
    public int maxPathSum(TreeNode root) {
        // Adopt depth first search
        // Step 1: Recursively solve this problem
        // Step 2: Get largest left sum and right sum
        // Step 3: Compare to the stored maximum        
        if (root == null)
            max = 0;
        else
            // Note: Some 'val' is negative number.
            max = root.val;
            
		findMax(root);
		
		return max;
	}
 
	public int findMax(TreeNode node)
	{
	    if (node == null)
		return 0;
 
	    // Recursively get sum of left and right path
	    int left = Math.max(findMax(node.left), 0);
	    int right = Math.max(findMax(node.right), 0);
 
	    // Get maximum path sum for current node
	    max = Math.max(node.val + left + right, max);
 
	    // Return sum of largest path for current node (left branch or right branch)
	    return node.val + Math.max(left, right);      
    }
}