力扣 hot100 Day52

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，实时比较更新就可以得到最终结果了。