Who can tell me how this is going?


  • 0
    I

    Fisrt, it can be tested successfully,like this:

    int maxDepth(struct TreeNode* root) {
    if (root == NULL) {
    return 0;
    } else {
    int dl = maxDepth(root->left) + 1;
    int dr = maxDepth(root->right) + 1;
    return dl>dr ? dl : dr;
    }
    }

    Submission Result: Accepted

    Then failed like this:

    int maxDepth(struct TreeNode* root) {
    if (root == NULL) {
    return 0;
    } else {
    return (maxDepth(root->left) + 1) > (maxDepth(root->right) + 1) ? maxDepth(root->left) + 1 : maxDepth(root->right) + 1;
    }
    }

    Submission Result: Time Limit Exceeded


    What the difference between them?


  • 2

    1.Time cost of your first method:
    T(n) = 2T(n / 2) + O(1)
    = O(n)

    2.Time cost of your second method:
    T(n) = 3T(n / 2) + O(1)
    = O( n ^ log2(3) )

    It's a big difference between those two method!
    That's why the second method shows Time Limit Exceeded


Log in to reply
 

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