題目

摘自LeetCode124

解題方法

選擇了一道LeetCode上難度為困難的遞歸求解的算法題。
算法如下：

1. 當前遍歷的節(jié)點為root，root是否在最大路徑中，需要計算root.val值與左右子樹返回的路徑的和，并且與現(xiàn)在最大路徑和進行比較，如果大于，則保存；

如下圖1，設(shè)root節(jié)點為20，計算黃色節(jié)點的和，判斷是否是最大的路徑和。

圖1

2. 遞歸返回值不是包括root的最大路徑和，而是root.val值與左右子樹路徑的大值的和；

遞歸返回值如下圖2，同樣設(shè)root節(jié)點為20，返回值為粉色節(jié)點和，20+15=35（因為15 > 7）

圖2

3.如果節(jié)點是空，返回0。同時如果左右子樹路徑是負值，不計入到最大路徑中（因為加負值只會讓路徑和更?。?/p>

代碼

public int maxPathSum(TreeNode root) {
    //定義長度為1的數(shù)組存儲最大路徑和
    int[] result = {Integer.MIN_VALUE};
    maxPathSumHelper(root, result);
    return result[0];
}
//遞歸尋找最大路徑和
private int maxPathSumHelper(TreeNode root, int[] result){
    //空節(jié)點返回0
    if(null == root){
        return 0;
    }
    //遞歸左子樹
    int leftMaxPath = maxPathSumHelper(root.left, result);
    //如果最大路徑大于0，則保留；小于0，則保留0
    leftMaxPath = leftMaxPath > 0 ? leftMaxPath : 0;
    //遞歸右子樹
    int rightMaxPath = maxPathSumHelper(root.right, result);
    //如果最大路徑大于0，則保留；小于0，則保留0
    rightMaxPath = rightMaxPath > 0 ? rightMaxPath : 0;
    //新的路徑和是當前節(jié)點加上左右子樹的路徑
    int newMaxPath = leftMaxPath + rightMaxPath + root.val;
    //如果大于當前的最大路徑和，則保留
    result[0] = newMaxPath > result[0] ? newMaxPath : result[0];
    //返回值是當前節(jié)點值與左右子樹路徑的大值的和
    return root.val + Math.max(leftMaxPath, rightMaxPath);
}