递归code

class Solution {
  int max_sum = Integer.MIN_VALUE;
  //返回node为根节点对应的单边最大路径值
  public int max_gain(TreeNode node) {
    if (node == null) return 0;  //递归终止条件
    // 递归计算左右子树从根节点出发的单边最大路径 如果小于0置为0
    int left_gain = Math.max(max_gain(node.left), 0);
    int right_gain = Math.max(max_gain(node.right), 0);
    // 计算包括根节点的双边路径值
    int price_newpath = node.val + left_gain + right_gain;
    // 如果超过最大路径则更新
    max_sum = Math.max(max_sum, price_newpath);
    //返回该树从该节点出发的最大路径
    return node.val + Math.max(left_gain, right_gain);
  }
  public int maxPathSum(TreeNode root) {
    //调用跟节点
    max_gain(root);
    //返回最后的最大路径和
    return max_sum;
  }
}