类型：树
-
- 二叉树中的最大路径和 ❤️
https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/
❓ 求二叉树中最大的路径和。路径至少包含一个结点，且不一定经过根结点。
💡 递归 + 贪心
class Solution: def __init__(self): self.maxSum = -2147483648 def maxPathSum(self, root: TreeNode) -> int: if not root: return 0 def dfs(node): if not node: return 0 leftSum = dfs(node.left) rightSum = dfs(node.right) self.maxSum = max(self.maxSum, max(leftSum, 0) + max(rightSum, 0) + node.val) return max(leftSum, rightSum, 0) + node.val dfs(root) return self.maxSum时间复杂度：O(n)，空间复杂度：O(n)