【leetcode----二叉树中的最大路径和】

二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

题目理解与分析：就是在二叉树中找到一条和最大的线。

解题思路：从上往下使用递归，1.迭代计算最大的左孩子长度，迭代计算最大的右孩子长度  2.计算每个节点加上左右孩子的最大长度作为最大值，并每个计算完与最大值比较更新。3. 判断左节点和右节点孰大孰小，更新节点的最大路径。

因为最长的线可能出现在：以叶节点为根的单个路径、以叶节点的父节点为根的回旋路径、以根节点为父节点的回旋路径/单个路径。所以归根到底是记录以每个节点为根的最大路径。

class TreeNode(object):def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = right
class Solution:def __init__(self):self.maxSum = float("-inf")def maxPathSum(self, root: TreeNode) -> int:def maxGain(node):if not node:return 0leftGain = max(maxGain(node.left), 0)rightGain = max(maxGain(node.right), 0)priceNewPath = node.val + leftGain + rightGainself.maxSum = max(self.maxSum, priceNewPath)return node.val + max(leftGain, rightGain)maxGain(root)return self.maxSum