Clean c++ solution


  • 10
    S
    class Solution {
        int res;
    public:
        int depth(TreeNode *root){
            if(root==NULL) return 0;
            int a=depth(root->left), b=depth(root->right);
            res=max(res,a+b+root->val);//if *root is the top node in the path
            return max(0,max(a, b)+root->val);//if *root is in the path, if this branch a burden or a plus
        }
        int maxPathSum(TreeNode *root) {
            if(root==NULL) return 0;
            res=root->val;
            depth(root);
            return res;
        }
    };

  • 0
    W

    I do not think the "if(root==NULL) return 0;" is necessary both in the tow function, only one in depth() is enough.


  • 0
    C
    This post is deleted!

  • 0
    A

    What is the complexity of this solution? I think the time is O(n), but the recursion makes the space complexity hard to understand.


  • -1
    D

    understand why such recurstion lsum, rsum and result is passed with pointer here at with same code and same example : http://goo.gl/wuatmP


  • 0
    D
    This post is deleted!

  • 0
    D
    This post is deleted!

  • 1
    L

    the res as a parameter is better:

    class Solution {
    public:
        int maxPathSum(TreeNode* root) {
            if(!root) return 0;
            int res = root->val;
            depth(root, res);
            return res;
    }
    private:
        int depth(TreeNode* root, int& res)
      {
           if(!root) return 0;
           int a = depth(root->left, res), b = depth(root->right, res);
           res = max(res, a+b+root->val);
           return max(0, max(a, b)+root->val);
      }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.