Re: [閒聊] 每日LeetCode
124. Binary Tree Maximum Path Sum
給你一個二元樹，找出最大的一個路徑和，路徑可以不通過root節點。
Example：
https://assets.leetcode.com/uploads/2020/10/13/exx1.jpg
Input: root = [1,2,3]
Output: 6
Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.
https://assets.leetcode.com/uploads/2020/10/13/exx2.jpg
Input: root = [-10,9,20,null,null,15,7]
Output: 42
Constraints:
-1000 <= Node.val <= 1000
思路：
1.我們可以把任意node的所有路徑切成四種情況：
(1) root本身就是最大路徑 [1,-1,-1]
(2) root + 左Path 是最大路徑 [1,1,-1]
(3) root + 右Path 是最大路徑 [1,-1,1]
(4) root + 左右Path是最大路徑 [1,1,1]
2.所以我們對樹做DFS並判斷上面的四種Case，不斷的更新max的值，當node為空的時候返
回下限值（-1001）即可。
3.需要注意的是DFS的返回值必須是root、root+左路徑、root+右路徑其中一個，因為
Path不能有兩個Edge。
Java Code：
------------------------------------------
class Solution {
private int max;
public int maxPathSum(TreeNode root) {
max = -1001;
dfs(root);
return max;
}
public int dfs(TreeNode root) {
if (root == null) {
return -1001;
}
int leftSum = dfs(root.left);
int rightSum = dfs(root.right);
int lPath = root.val + leftSum;
int rPath = root.val + rightSum;
int rootPath = lPath + rightSum;
max = Math.max(max, root.val);
max = Math.max(max, lPath);
max = Math.max(max, rPath);
max = Math.max(max, rootPath);
return Math.max(root.val, Math.max(lPath, rPath));
}
}
------------------------------------------
--
https://i.imgur.com/tdaniED.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.75.86 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1670740091.A.9B4.html
推
12/11 14:29,
3年前
, 1F
12/11 14:29, 1F
推
12/11 14:30,
3年前
, 2F
12/11 14:30, 2F
推
12/11 14:34,
3年前
, 3F
12/11 14:34, 3F
推
12/11 14:35,
3年前
, 4F
12/11 14:35, 4F
討論串 (同標題文章)
完整討論串 (本文為第 133 之 719 篇)：