My recursive solution (C++)


  • 1
    D
    // To search the maximum branch rooted at Node root, and also update the maxPath, which is the currently founded max path
    int maxBranchSearch(TreeNode *root, int &maxPath){
        int maxL, maxR;
        if(!root)
        {// if a empty tree, then the maximum branch is 0
            return 0;
        }
        else
        {
            maxL = max(maxBranchSearch(root->left, maxPath), 0); // find the maximum branch rooted at root->left,  it can be empty (0)
            maxR = max(maxBranchSearch(root->right, maxPath),0);// find the maximum branch rooted at root->right, it can be empty (0)
            maxPath = max(maxPath, maxL + root->val + maxR); // update the maximum path, it is either the old one, or a one passing through root
            return max(maxL, maxR) + root->val; // the maximum branch rooted at root is either root + max_branch of left/right, or root itself
        }
    }
    
    int maxPathSum(TreeNode *root) {
        int maxPath = INT_MIN;
        maxBranchSearch(root, maxPath);
        return maxPath;
    }

Log in to reply
 

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