Java recursive solution. Accepted.


  • 1
    P

    The recursive function returns a longest left or right path. And here inside we calculate max sum. Which nodes value plus left side sum plus right side sum.

    private int mMax = Integer.MIN_VALUE;
    
    public int maxPathSum(TreeNode root) {
    	pathSum(root);
    	return mMax;
    }
    
    public int pathSum(TreeNode node) {
    	int sum = node.val;
    	int left = node.left != null ? pathSum(node.left) : 0;
    	int right = node.right != null ? pathSum(node.right) : 0;
    	left = left > 0 ? left : 0;
    	right = right > 0 ? right : 0;
    	int side = left > right ? left : right;
    	sum += left + right;
    	if (sum > mMax) {
    		mMax = sum;
    	}
    	return node.val + side;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.