124. Binary Tree Maximum Path Sum

おもしろい問題ですが、hard tagとは言えません.ここではmax(int[]はglobalを使用しないため)を記録してmax path sum(任意のnodeを起点として終点とすることができ、path全体が1つのnode以上であればよい.ここでnode値は負であってもよいことに注意する.
helper関数の定義はrootを最高根として見つけられるmax sum pathのsum値であり、rootの左子と右子を最高点として見つけられるmax sum pathのsumをそれぞれ求める.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 
 
        1
      /   \
     2     3
    / \   / \
   5   3 9   4
 
max[0]: maxPathSum  
helper method 1.returns path sum that can be extended to the parent of input root 5-2 can, 5-2-3 can not 
              2.computes max path sum with higest node the input root (left + right + root.val) and update the max path sum   
use max(0, helper(root.left, max))  to calculate left and right to avoid change codes when l,r < 0
 */
class Solution {
    public int maxPathSum(TreeNode root) {
        if (root == null){
            return 0;
        }
        int[] max = new int[1];
        max[0] = Integer.MIN_VALUE;
        helper(root, max);
        return max[0];   
    }
    
    private int helper(TreeNode root, int[] max){
        if (root == null){
            return 0;
        }
        int left = Math.max(0,helper(root.left, max));
        int right = Math.max(0,helper(root.right, max));
        max[0] = Math.max(max[0],left + right + root.val);
        return Math.max(left, right) + root.val;
    }
}