點選藍色“五分鐘學算法”關注我喲
加個“星标”，天天中午 12:15，一起學算法
作者 | P.yh
來源 | 五分鐘學算法
題目描述
給定一個非空二叉樹，傳回其最大路徑和。
本題中，路徑被定義為一條從樹中任意節點出發，達到任意節點的序列。該路徑 至少包含一個節點 ，且不一定經過根節點。
示例 1:
輸入: [1,2,3]
1
/ \
2 3
輸出: 6
示例 2:
輸入: [-10,9,20,null,null,15,7]
-10
/ \
9 20
/ \
15 7
輸出: 42
題目分析
這是一道二叉樹問題中比較難的題目。
題目要求出一個二叉樹的最大路徑和，路徑和就是把一條路徑上面節點的值加起來，這一題的難點在于路徑的方向不固定，隻要是任意兩點間的通路都算是有效路徑。
一般來說，解決樹的問題都需要用到遞歸，樹上的搜尋，本質上也是深度優先搜尋。
這裡會有兩種考慮方式，一個是自底向上的分治，也就是進入遞歸，一開始不做任何節點上面的計算或者是處理，直接進入到下一層遞歸，直到到了最底層，然後再開始計算并傳回答案，然後上層樹節點的遞歸函數就會收到下層傳回的結果，這樣做的好處是，一個節點可以獲知其子樹的局部答案；
另外一個是自頂向下的周遊搜尋，這個和之前的思路完全相反，也就是先處理目前節點的内容，處理完後去到下一層節點，這種方法一般沒有傳回值，但是一般會有一個全局或者是引用變量，用來記錄周遊過程中的内容。
我們再回過頭來看這道題，在遞歸周遊的過程中，對于目前節點，其在路徑中可以是路徑尾，路徑頭(假設路徑是從上到下的，其實在這道題中，沒有頭尾的概念)，也可以是路徑中的一個節點。
那怎麼判斷呢？
這時我們得需要目前節點左右子樹的資訊，是以我們可以考慮使用之前提到的 自底向上 的分治，有了目前節點，左右子樹到目前節點的最大路徑，我們可以看看這裡會有幾種情況，我用 root 表示目前節點，left 表示左子樹到 root 的最大和的路徑，right 表示右子樹到 root 的最大和的路徑：
- root 和左右路徑形成路徑(left - root - right)
- root 和左路徑形成路徑(left - root)
- root 和右路徑形成路徑(root - right)
- root 自成路徑(root)
你可以看到這四種情況都會把目前節點考慮在内，我們可以更新這裡的最大值。
但是需要注意的是，我們傳回的時候，第一種情況是不能傳回的，因為對于上一層節點來說，其無法形成有效的路徑，是以我們隻需要将 2，3，4 中的最大值傳回即可，當然，更新全局答案的時候，這 4 種情況都需要考慮在内的。
動畫描述
代碼實作
private int maximum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
if (root == null) {
return 0;
}
helper(root);
return maximum;
}
private int helper(TreeNode root) {
if (root == null) {
return 0;
}
// 如果左右子樹傳回的最大路徑值小于 0
// 直接将值設為 0，也就是不考慮對應的路徑
int leftMax = Math.max(0, helper(root.left));
int rightMax = Math.max(0, helper(root.right));
//自底向上的分治,直到到了最底層，才開始計算并傳回答案
maximum = Math.max(root.val + leftMax + rightMax, maximum);
return Math.max(leftMax + root.val, rightMax + root.val);
} 
● 用好這 42 款 Chrome 插件，每年輕松省出一個年假
● 【算法之美】改變世界的十位算法大師
● 把 14 億中國人都拉到一個微信群在技術上能實作嗎？
● 全球最厲害的 14 位程式員！
— 完 —