前言

本題為 LeetCode 前 100 高頻題

我們社區(qū)陸續(xù)會(huì)將顧毅（Netflix 增長(zhǎng)黑客，《iOS 面試之道》作者，ACE 職業(yè)健身教練。）的 Swift 算法題題解整理為文字版以方便大家學(xué)習(xí)與閱讀。

LeetCode 算法到目前我們已經(jīng)更新到 123 期，我們會(huì)保持更新時(shí)間和進(jìn)度（周一、周三、周五早上 9:00 發(fā)布），每期的內(nèi)容不多，我們希望大家可以在上班路上閱讀，長(zhǎng)久積累會(huì)有很大提升。

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

難度水平：困難

1. 描述

路徑 被定義為一條從樹中任意節(jié)點(diǎn)出發(fā)，沿父節(jié)點(diǎn)-子節(jié)點(diǎn)連接，達(dá)到任意節(jié)點(diǎn)的序列。同一個(gè)節(jié)點(diǎn)在一條路徑序列中 至多出現(xiàn)一次 。該路徑 至少包含一個(gè) 節(jié)點(diǎn)，且不一定經(jīng)過根節(jié)點(diǎn)。

路徑和 是路徑中各節(jié)點(diǎn)值的總和。

給你一個(gè)二叉樹的根節(jié)點(diǎn) root ，返回其 最大路徑和 。

2. 示例

示例 1

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

示例 2

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

約束條件：

• 樹中節(jié)點(diǎn)數(shù)目范圍是 [1, 3 * 10^4]
• -1000 <= Node.val <= 1000

3. 答案

/**
 * 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)
    }
}

• 主要思想：迭代所有樹節(jié)點(diǎn)，計(jì)算每個(gè)節(jié)點(diǎn)的最大權(quán)值，并在迭代過程中更新最大路徑和。
• 時(shí)間復(fù)雜度： O(n)
• 空間復(fù)雜度： O(1)

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

點(diǎn)擊前往 LeetCode 練習(xí)

關(guān)于我們

我們是由 Swift 愛好者共同維護(hù)，我們會(huì)分享以 Swift 實(shí)戰(zhàn)、SwiftUI、Swift 基礎(chǔ)為核心的技術(shù)內(nèi)容，也整理收集優(yōu)秀的學(xué)習(xí)資料。

后續(xù)還會(huì)翻譯大量資料到我們公眾號(hào)，有感興趣的朋友，可以加入我們。