二叉树中的最大路径和

题目描述

1. 类似于从数组中找到最大子数组。
2. 不同于寻找二叉树的最大直径。

https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/

思路

1. 首先转换为寻找每个节点的最大贡献值：即以该节点为起点的最大路径和，这就有点类似于数组中的最大子数组了。
2. 依次遍历每个节点，寻找经过该点的最大路径和；就是该节点加上左右子树的最大贡献值。（其实最优的最大路径和未必需要加上该节点，所以这里只是在求一个局部最优）
3. 然后和全局的最大路径和作比较。