[数据结构与算法]牛客NC6 / LeetCode 124二叉树的最大路径之和

题目：给定一个二叉树根节点，返回最大路径之和

题目重点：

• 路径：任意一个节点到另一节点之间的路径
• 每个节点只能出现一次
• 不一定通过根节点
• 路径和：路径中各个节点的值

示例1：

		1
	  /   \
	 2     3
输出：6  

示例2：

   -10
   /  \
  9   20
     /  \
    15   7
输出：42

解析： 本题本质上就是二叉树的后序遍历。

• 首先写边界条件，如果根为null，那么最大路径和就是0。
• 我们从示例2，以20为根的树来分析，这个树的最大路径和就是：15+7+20=35。但如果15变成了-15，那么这个树的最大路径就是：7+20=27。所以我们可以认为，如果节点值小于0我们就舍弃，同理可认为，如果一个节点的和的最大值小于0我们就舍弃（节点和的最大值：对于示例2整体分析，-10的右子树的节点和的最大值就是15+20=35）。
  代码：

class Solution {
    int max = Integer.MIN_VALUE; 
    public int maxPathSum(TreeNode root) {
        dg(root);  
        //max才是递归方法里真正的解    
        return max;
    }
    //dg递归的意思
    public int dg(TreeNode node) {
        if (node == null) {
            return 0;
        }      
        // 递归计算左右子节点和的最大值
        // 只有在和的最大值大于 0 时，才会选取对应子节点
        int left = Math.max(dg(node.left), 0);
        int right = Math.max(dg(node.right), 0);

        // 节点的最大路径和取决于该节点的值与该节点的左右子节点的和的最大值
        int price = node.val + left + right;

        // 更新答案
        max = Math.max(max, price);

        // 返回节点和的最大值，因为节点不能重复，所以对于任意一个节点的最大值只能是根节点+max(左子树，右子树)
        return node.val + Math.max(left, right);
    }
}