Binary Tree Maximum Path Sum

二叉树中的最大路径和

题目

Given a non-empty 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 contain at least one node and does not need to go through the root.

Example 1:

Input: [1,2,3]

  1
 / \
2   3

Output: 6
Example 2:

Input: [-10,9,20,null,null,15,7]

-10
/ \
9 20
/ \
15 7

Output: 42

解析重点

1.最大路径和，我们需要递归计算路径的和，然后把最大的路径和存储起来。当路径上的和小于0时，我们需要舍弃这部分节点。同时我们还需要比较左右节点，路径大的
一边才是我们需要的。

java代码

class Solution {
    int max;

    public int maxPathSum(TreeNode root) {
        max = Integer.MIN_VALUE;
        maxCySum(root);
        return max;
    }

    int maxCySum(TreeNode root) {
        if (root == null) return 0;
        int left = Math.max(0, maxCySum(root.left));//左节点路径和，当左节点小于0时舍弃
        int right = Math.max(0, maxCySum(root.right));//右节点路径和，当右节点小于0时舍弃
        max = Math.max(max, left + right + root.val);//累计计算max，保存最大的max
        return Math.max(left, right) + root.val;//返回路径和大的路径和
    }
}