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 must containat least one nodeand does not need to go through the root.

For example:
Given the below binary tree,

      1
      / \
     2   3

Return6.

代码

class Solution {
    public int maxPathSum(TreeNode root) {

        return dfs(root)._fullMax;
    }

    private Result dfs(TreeNode node) {
        if (node == null) {
            return new Result(0, Integer.MIN_VALUE);

        }

        Result leftResult = dfs(node.left);
        Result rightResult = dfs(node.right);

        int partialMax = node.val + max(0, leftResult._partialMax, rightResult._partialMax);
        int fullMax = max(leftResult._fullMax, rightResult._fullMax, node.val+
                max(0, leftResult._partialMax, rightResult._partialMax, 
                    leftResult._partialMax + rightResult._partialMax));
        return new Result(partialMax, fullMax);
    }

    private int max(int... array) {
        int result = array[0];
        for (int i = 1; i < array.length; i++) {
            result = Math.max(result, array[i]);

        }
        return result;

    }

    private class Result {
        int _partialMax;
        int _fullMax;

        Result(int partialMax, int fullMax) {
            _partialMax = partialMax;
            _fullMax = fullMax;

        }
    }
}