My recursive solution (C++)

  • 1
    // 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 a empty tree, then the maximum branch is 0
            return 0;
            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.