124. 二叉樹中的最大路徑和

二叉樹中的?路徑?被定義為一條節點序列，序列中每對相鄰節點之間都存在一條邊。同一個節點在一條路徑序列中?至多出現一次?。該路徑?至少包含一個?節點，且不一定經過根節點。

路徑和?是路徑中各節點值的總和。

給你一個二叉樹的根節點?root?，返回其?最大路徑和?。

//自己寫的
class Solution {
public:int maxpasssum(TreeNode* root,int& maxtmp){if(!root) return 0;int leftmaxsum = max(maxpasssum(root->left,maxtmp),0);int rightmaxsum = max(maxpasssum(root->right,maxtmp),0);maxtmp = max(maxtmp,leftmaxsum+rightmaxsum+root->val);return root->val+max(leftmaxsum,rightmaxsum);}int maxPathSum(TreeNode* root) {int maxtmp = INT_MIN;maxpasssum(root,maxtmp);return maxtmp;        }
};

邏輯有點像求二叉樹的最大深度，都是需要在遞歸過程中間進行判斷再回溯

本題需要考慮的是，對于遞歸到的根節點來說，最大路徑和可能并不經過該節點，所以需要引入一個maxtmp進行存儲。

這里maxpasssum返回值含義是，目前經過該節點的最大單向路徑和（不橫跨左右子樹），left/rightmaxsum則為其左右子樹返回的對應值與0的最大值（返回值可能小于0，此時取零相當于不考慮加上這條分支了）

由此可以遞推對于任意節點，新出現的可能最大路徑和為leftmaxsum+rightmaxsum+root->val，實時比較更新就可以得到最終結果了。