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

推 wwndbk: 大師 12/11 14:29

推 pandix: 大師 12/11 14:30

推 ririoshi: 大師 12/11 14:34

推 DDFox: 大師 12/11 14:35