二叉树中的最大路径和

描述

困难 给定一个非空二叉树，返回其最大路径和。

本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

示例 1:

输入: [1,2,3] 1 / \ 2 3 输出: 6

示例 2:

输入: [-10,9,20,null,null,15,7]   -10    / \   9  20     /  \    15   7 输出: 42

解题

对于一个节点来说，最大路径和有4种情况

只有当前节点当前节点 + 左子树当前节点 + 右子树当前节点 + 左子树 + 右子树

获取父节点的路径最大值时 其子节点只能采取前三种路径方式，即不能同时出现左和右子树 表现在递归函数中，其返回值为前三种方式的最大值

# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def __init__(self): self.result = -100000 def maxPathSum(self, root: TreeNode) -> int: self.maxValue(root) return self.result def maxValue(self, root): if not root: return 0 left = self.maxValue(root.left) right = self.maxValue(root.right) # 四种不同的路径方案 value1 = root.val value2 = root.val + left value3 = root.val + right value4 = root.val + left + right self.result = max(max([value1, value2, value3, value4]), self.result) # 去除第四种情况求得最大值 return max([value1, value2, value3])