LeetCode - #124 二叉樹中的最大路徑和（Top 100）_Swift社群

持續創作，加速成長！這是我參與「掘金日新計劃 · 6 月更文挑戰」的第35天，點選檢視活動詳情

前言

本題為 LeetCode 前 100 高頻題

我們社群陸續會將顧毅（Netflix 增長黑客，《iOS 面試之道》作者，ACE 職業健身教練。）的 Swift 演算法題題解整理為文字版以方便大家學習與閱讀。

LeetCode 演算法到目前我們已經更新到 123 期，我們會保持更新時間和進度（週一、週三、週五早上 9:00 釋出），每期的內容不多，我們希望大家可以在上班路上閱讀，長久積累會有很大提升。

不積跬步，無以至千里；不積小流，無以成江海，Swift社群伴你前行。如果大家有建議和意見歡迎在文末留言，我們會盡力滿足大家的需求。

難度水平：困難

1. 描述

路徑被定義為一條從樹中任意節點出發，沿父節點-子節點連線，達到任意節點的序列。同一個節點在一條路徑序列中 至多出現一次 。該路徑 至少包含一個 節點，且不一定經過根節點。

路徑和 是路徑中各節點值的總和。

給你一個二叉樹的根節點 root ，返回其 最大路徑和 。

2. 示例

示例 1

輸入：root = [1,2,3] 輸出：6 解釋：最優路徑是 2 -> 1 -> 3 ，路徑和為 2 + 1 + 3 = 6

示例 2

輸入：root = [-10,9,20,null,null,15,7] 輸出：42 解釋：最優路徑是 15 -> 20 -> 7 ，路徑和為 15 + 20 + 7 = 42

約束條件：

樹中節點數目範圍是 [1, 3 * 10^4]
-1000 <= Node.val <= 1000

3. 答案

```swift / * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode left, TreeNode right) : val(x), left(left), right(right) {} * }; */

class BinaryTreeMaximumPathSum {

var maxValue = Int.min

func maxPathSum(_ root: TreeNode?) -> Int {
    maxWeight(root)
    return maxValue
}

private func maxWeight(_ node: TreeNode?) -> Int {
    guard let node = node else {
        return 0
    }

    let leftMaxWeight = max(maxWeight(node.left), 0)
    let rightMaxWeight = max(maxWeight(node.right), 0)

    maxValue = max(maxValue, leftMaxWeight + node.val + rightMaxWeight)

    return node.val + max(leftMaxWeight, rightMaxWeight)
}

} ```

主要思想：迭代所有樹節點，計算每個節點的最大權值，並在迭代過程中更新最大路徑和。
時間複雜度： O(n)
空間複雜度： O(1)

該演算法題解的倉庫：LeetCode-Swift

點選前往 LeetCode 練習

關於我們

我們是由 Swift 愛好者共同維護，我們會分享以 Swift 實戰、SwiftUI、Swift 基礎為核心的技術內容，也整理收集優秀的學習資料。