Leetcode | Binary Tree Maximum Path Sum

given a binary tree, find the maximum path sum.

the path may start and end at any node in the tree.

for example:

given the below binary tree,

1

/ \

2 3

return 6.

最大值是以下几种情况的最大值：

1. 左子树的最大值；

2. 右子树的最大值；

3. 部分path在左子树，部分path在右子树，经过root；

1和2很多计算，在递归中保持就行，这里用maxdouble表示（两边都有）；

3的话需要维护止于root点的最大值，这里用maxsingle表示（只有一边，止于root）；

初始值的话不能设成0、-1之类的某个数，因为这些数可能出现，也可能不出现，因为是最大值比较，所以用int_min；

maxsingle很好求，可以先求左右maxsingle的最大值，如果这个值是正数，那么可以把root也算上，不然就直接是root了。

maxdouble至少是maxsingle，然后再和左右子树的maxdouble比，最后和经过root，包含左右子树的情况相比。注意的是排除掉左右子树为空的情况。

cheers！庆祝leetcode终于刷了100题。44天，当然中间大部分时间是要忙实验室的活，还有放假出去玩的时间，真正在做的时间一般多。