# 0124. Binary Tree Maximum Path Sum
###### tags: `Leetcode` `Hard` `DFS`
Link: https://leetcode.com/problems/binary-tree-maximum-path-sum/
## 思路
和[543. Diameter of binary tree](https://hackmd.io/FPZpR3NBQuCV_u2vTZaEvQ) 有点像
都是做dfs，return 当前node下，只计算一边的最大长度/最大值，然后在过程中记录计算两条边的最大长度/最大值
但区别是周长加上左子树和右子树的结果一定比只加一个或都不加大，但是pathsum要比较这几种情况的结果

要注意的是这道题在return的时候，**除了要比较左边能得到的最大值和右边能得到的最大值，还要比较自身node的值**（因为有可能自身node的值，比左边最大值+node.val或右边最大值+node.val都大）

## Code

class Solution {
    int maxSum = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        maxSidePathSum(root);
        return maxSum;
    }
    public int maxSidePathSum(TreeNode root){
        if(root == null){
            maxSum = Math.max(maxSum, 0);
            return 0;
        }
        int leftPathSum = root.left == null?0:maxSidePathSum(root.left);
        int rightPathSum = root.right == null?0:maxSidePathSum(root.right);
        
        maxSum = Math.max(maxSum, Math.max(root.val,Math.max(leftPathSum+rightPathSum+root.val, Math.max(leftPathSum+root.val, rightPathSum+root.val))));
        return Math.max(root.val,Math.max(leftPathSum,rightPathSum)+root.val);
        
    }
}