C++, DFS, recursion


  • 0
    T
    class Solution {
    private:
        int maxPathSumHelper(TreeNode* root, int* max)
        {   
            // DFS: depth first search
            if(root == NULL)
                return 0;
            int left = maxPathSumHelper(root->left, max);
            int right = maxPathSumHelper(root->right, max);
            int three = root->val;
            if(left > 0)
                three = three + left;
            if(right > 0)
                three = three + right;
            if(three > *max)
                *max = three;
                
            int two = root->val;
            if(left > right && left > 0)
                two = two + left;
            else if(right > left && right > 0)
                two = two + right;
            return two;
        }
    public:
        int maxPathSum(TreeNode* root) {
            int max = INT_MIN;
            maxPathSumHelper(root, &max);
            return max;
        }
    };

Log in to reply
 

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