Re: [閒聊] 每日LeetCode

作者: Rushia (みけねこ的鼻屎)   2022-12-11 14:28:08
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:
作者: wwndbk (黑人問號)   2022-12-11 14:29:00
大師
作者: pandix (麵包屌)   2022-12-11 14:30:00
大師
作者: ririoshi (角落住民)   2022-12-11 14:34:00
大師
作者: DDFox (冒險者兼清潔工)   2022-12-11 14:35:00
大師

Links booklink

Contact Us: admin [ a t ] ucptt.com