二叉樹中的最大路徑和
題目：
給定一個非空二叉樹，回傳其最大路徑和，
本題中，路徑被定義為一條從樹中任意節點出發，沿父節點-子節點連接，達到任意節點的序列，該路徑至少包含一個節點，且不一定經過根節點，
示例 1：
1
/ \
2 3
輸出：6
示例 2：
-10
/ \
9 20
/ \
15 7
輸出：42
思路
路徑每到一個節點，我們有三種選擇，
1.停留在節點
2.走向左子節點
3.走向右子節點
走到下一個節點后，我們又要面臨這樣的選擇，
故可以使用遞回的思路
（注意 不能既走左子節點又走右子節點，這樣將會導致路徑重復）
我們只需關心從子樹中獲取最大收益，而無需關心具體的實作路徑，這就是一種遞回、自頂向下的思考，
我們定義深度優先搜索DFS函式，用于求出子樹中的最大路徑和，
還是分為三種情況：
1.停留在當前節點 收益： node.val
2.走入左子樹 收益： node.val +leftPathSum
3.走入右子樹 收益： node.val +rightPathSum
如果左右子樹收益為負，我們則舍棄之，即：
leftPathSum = Math.max(DFS(node.left), 0);
rightPathSum = Math.max(DFS(node.right), 0);
題目還說不一定經過根節點，說明最大路徑和可能存在區域子樹中，則我們需要在每一次遞回時求一下當前的最大路徑和，
如果能夠明白上述思路，就可以清楚明白我們的代碼，
class Solution {
int maxSum = Integer.MIN_VALUE; // 記錄最大路徑和
public int maxPathSum(TreeNode root) {
DFS(root);
return maxSum;
}
public int DFS(TreeNode node) {
if (node == null)
return 0;
int leftPathSum = Math.max(DFS(node.left), 0);
int rightPathSum = Math.max(DFS(node.right), 0);
// 每次遞回時求最大路徑和
maxSum = Math.max(maxSum, node.val + leftPathSum + rightPathSum);
// 回傳子樹的最大路徑和
return node.val + Math.max(leftPathSum, rightPathSum);
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/66534.html
標籤：其他