leetcode | binary tree maximum path sum java[二叉树最大路径和]

　　Binary Tree Maximum Path Sum

　　leetcode 原题链接：https://leetcode.com/problems/binary-tree-maximum-path-sum/

　　题目如图所示：

　　刚看到这道题的时候，并没有想到很好的解决方案，主要困惑集中在，最大路径起点终点的选择可以是任意的。就是说关于某一个节点的最大路径可能有两种情况：1.是这个node向下走到某个点终止的一条路径，2. 是从该节点的左子树的某一个节点，跨过该节点，到该节点右子树某个节点终止的一条路径。想到这里，就已经感觉问题非常复杂了。

　　幸好，这个题的大方向是有的，就是递归，递归树的每一个节点，然后寻找相关路径。最后，在google出了一个很巧妙地答案，通过新建一个内部类来表示节点的最大路径的两种情况。这样，问题就简化成了单纯的树的递归问题了。

　　代码：

　　public class Solution {
　　public int maxPathSum(TreeNode root) {
　　ResultType rst = maxPathSumHelper(root);
　　return rst.maxPath;
　　}
　　public class ResultType {
　　int singlePath;
　　int maxPath;
　　public ResultType(int s, int m){
　　this.singlePath = s;
　　this.maxPath = m;
　　}
　　}
　　public ResultType maxPathSumHelper(TreeNode root){
　　if(root == null){
　　return new ResultType(0, Integer.MIN_VALUE);
　　}
　　ResultType left = maxPathSumHelper(root.left);
　　ResultType right = maxPathSumHelper(root.right);
　　int singlePath = Math.max(left.singlePath, right.singlePath) + 
root.val;
　　singlePath = Math.max(singlePath, 0);
　　int maxPath = Math.max(left.maxPath, right.maxPath);
　　maxPath = Math.max(maxPath, left.singlePath+right.singlePath+root.val);
　　return new ResultType(singlePath, maxPath);
　　}
　　}

　　代码中，ResultType就是这个内部类，singlePath表示从节点开始的直线路径，maxPath表示关于这个节点的最大路径。