前言
本题为 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. 答案
/**
* 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 基础为核心的技术内容，也整理收集优秀的学习资料。
后续还会翻译大量资料到我们公众号，有感兴趣的朋友，可以加入我们。
