Leetcode 124 Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path does not need to go through the root.

For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6.

Solution 1: recursive DFS

 public class Solution {  
   public int maxPathSum(TreeNode root) {  
     int[] res=new int[1];  
     res[0]=Integer.MIN_VALUE;  
     dfs(root,res);  
     return res[0];  
   }  
   private int dfs(TreeNode x, int[] res) {  
     if (x==null) return 0;  
     int left=dfs(x.left,res);  
     int right=dfs(x.right,res);  
     int num=x.val;  
     if (left>0) num+=left;  
     if (right>0) num+=right;  
     if (num>res[0]) res[0]=num;  
     int max=Math.max(left,right);  
     if (max>0) return max+x.val;  
     return x.val;  
   }  
 }