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天，當然中間大部分時間是要忙實驗室的活，還有放假出去玩的時間，真正在做的時間一般多。