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.

分析

public class Solution {
    //instance variable
    private Integer Max = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        helper(root);
        return Max;
    }

    private int helper(TreeNode root) {
        int tempMax = Integer.MIN_VALUE;
        //base case 
        if(root == null) return 0;

        //recursive
        int leftMax = helper(root.left);
        int rightMax = helper(root.right);

        //node root is corner of path
        int temp1 = root.val + leftMax + rightMax;

        //node root is not corner of path
        int temp2 = Math.max(root.val + leftMax, root.val + rightMax);
        int temp3 =  root.val;

        tempMax = Math.max(temp1, Math.max(temp2, temp3));
        if(tempMax > Max) Max = tempMax;

        return Math.max(temp2, temp3);
    }
}