题解 | #二叉树中的最大路径和#
二叉树中的最大路径和
http://www.nowcoder.com/practice/da785ea0f64b442488c125b441a4ba4a
后根遍历
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
class Solution {
public:
/**
*
* @param root TreeNode类
* @return int整型
*/
void help(TreeNode* root,int &res){
if(root==NULL) return ;
help(root->left,res);
help(root->right,res);
int l=0,r=0;
if(root->left&&root->left->val>0) l=root->left->val;
if(root->right&&root->right->val>0) r=root->right->val;
res=max(res,root->val+r+l);
root->val+=max(l,r);
}
int maxPathSum(TreeNode* root) {
// write code here
int res=INT_MIN;
help(root,res);
return res;
}
};
查看17道真题和解析
