Leetcode124最大路径和

leetcode 124最大路径和 自己写的时候犯的错误

给定一个非空二叉树，返回其最大路径和。

本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

class Solution { public: int maxPathSum(TreeNode* root) { pathsum(root); return totalm; } private: int currm; int totalm = INT_MIN; int ls = 0,rs = 0; int pathsum(TreeNode* root){ if(!root) return 0; ls = pathsum(root->left); cout<<"ls:"<<ls<<endl; rs = pathsum(root->right); cout<<"rs:"<<rs<<endl; currm = root->val+max(0,ls)+max(0,rs); totalm = max(currm,totalm); return max(ls,rs)+root->val; } };

注意用递归求解， 递归的分量不能写到递归函数外面，当作全局变量。 就是代码中int ls = 0,int rs = 0; 这句话应该放到 int pathsum函数体中，因为ls,rs都是当前递归函数的暂时状态，返回给上一级的时候，需要回收，如果写到pathsum函数外面，那么ls和rs就只会记住递归最深处的ls和rs状态。

class Solution { public: int maxPathSum(TreeNode* root) { pathsum(root); return totalm; } private: int currm; int totalm = INT_MIN; int pathsum(TreeNode* root){ if(!root) return 0; int ls = pathsum(root->left); int rs = pathsum(root->right); currm = root->val+max(0,ls)+max(0,rs); totalm = max(currm,totalm); return max(ls,rs)+root->val; } };

正确代码如上。