前言
本題為 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ì)有很大提升涛目。
不積跬步，無(wú)以至千里凛澎；不積小流霹肝，無(wú)以成江海，Swift社區(qū) 伴你前行塑煎。如果大家有建議和意見(jiàn)歡迎在文末留言沫换，我們會(huì)盡力滿足大家的需求。
難度水平：困難
1. 描述
路徑 被定義為一條從樹(shù)中任意節(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)過(guò)根節(jié)點(diǎn)。
路徑和 是路徑中各節(jié)點(diǎn)值的總和雀哨。
給你一個(gè)二叉樹(shù)的根節(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
約束條件：
- 樹(shù)中節(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)
}
}
- 主要思想：迭代所有樹(shù)節(jié)點(diǎn)，計(jì)算每個(gè)節(jié)點(diǎn)的最大權(quán)值捌浩，并在迭代過(guò)程中更新最大路徑和放刨。
- 時(shí)間復(fù)雜度： O(n)
- 空間復(fù)雜度： O(1)
該算法題解的倉(cāng)庫(kù)：LeetCode-Swift
點(diǎn)擊前往 LeetCode 練習(xí)
關(guān)于我們
我們是由 Swift 愛(ài)好者共同維護(hù)，我們會(huì)分享以 Swift 實(shí)戰(zhàn)尸饺、SwiftUI进统、Swift 基礎(chǔ)為核心的技術(shù)內(nèi)容拓诸，也整理收集優(yōu)秀的學(xué)習(xí)資料。
后續(xù)還會(huì)翻譯大量資料到我們公眾號(hào)麻昼，有感興趣的朋友，可以加入我們馋辈。
