题目
二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。
示例 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 * 104]
- -1000 <= Node.val <= 1000
我的代码（Python）
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def maxPathSum(self, root: Optional[TreeNode]) -> int:
def innerCal(root: TreeNode) -> (int, int):
# inner max and max with root
if not root.left and not root.right:
return (root.val, root.val)
elif not root.right:
lim, lrm = innerCal(root.left)
return (max(lim, lrm + root.val, root.val), max(root.val, lrm + root.val))
elif not root.left:
rim, rrm = innerCal(root.right)
return (max(rim, rrm + root.val, root.val), max(root.val, rrm + root.val))
else:
lim, lrm = innerCal(root.left)
rim, rrm = innerCal(root.right)
return (max(root.val, lim, rim, lrm + root.val, rrm + root.val, lrm + root.val + rrm), max(root.val, lrm + root.val, rrm + root.val))
im, rm = innerCal(root)
return max(im, rm)点评
递归，计算每个子树的内部最大路径和以及以子树根结点为起始的最大路径和，在父结点中判定和计算，往上延伸至根结点即可。
判断条件是比较容易出错的地方，以及左右子树为空和不为空时的判断也容易出错。单纯用0来取代一些计算结果，如果所有数都是负数，很容易出问题。
和官方题解的思路是一样的。不过比官方啰嗦一些，像之前的一个题目：543. 二叉树的直径
我的解法一样。这个比较过程中第一个值，即内部最大路径没必要一直计算，可以通过一个全局变量来优化。
baddif@gmail.com
AI简历优化站
AI求职跟踪器（建设中）
主站（建设中）
相关平台
Github Issues / Notion / Blog