Using a max function to solve this


  • -1
    D
    int maxDepth(TreeNode *root) {
        // if (root == null)
            // return 0;
        return max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }
    
    int max (int x, int y){
        return x > y ? x : y;
    }
    

    I get a runtime error with Last executed input: {}

    I am a bit confused why this doesn't work. This is normally what I use when I do this problem. I was reading something similar and they said it was making a call later than when the solution checked it, but I'm not so sure that is happening here.


  • 0
    M

    What do you mean by "doesn't work?" Wrong answer? Time Limit? What test case failed? What was the expected answer? All these would make answering easier.


  • 4
    M

    With the if(root == null) return null; removed, your return value is attempting to access a property of a null struct, which causes the runtime error. I'm not sure why it would say null doesn't exist, but if it still says that, I suggest using if(!root) instead. In C++, null is equal to a pointer value of 0, and !0 evaluates to true for a conditional.


  • 0
    D

    Yeah that worked. Thanks a bunch.


  • 0
    E

    But it works in java, I guess it's because java doesn't use any pointer. However, when I use

    return (maxDepth(root.left) > maxDepth(root.right)? maxDepth(root.left) : maxDepth(root.right))+1; 
    

    instead of max function.
    Time Limit Exceeded error occurs.


  • 0
    S

    if null.left returns null, then maxDepth(null) calls maxDepth(null), which is infinite recursion. If it didn't time out, it would eventually overflow the stack. Doesn't Jave give a null pointer exception when you try to treat null as if it were an instance of a class?

    Without using max function (or saving results in variables) you're making each recursive call twice, at each level. What's the time complexity of that?


  • 0
    E

    Thank you so much. Now I can understand the overflow, but what does making each recursive call twice at each level mean?


  • 0
    S

    "Overflow" usually means something quite different from "Stack overflow".

    In the expression in your comment, you make the recursive calls on each of ->left and ->right in order to compare the results, then you make one of those same calls again, unnecessarily repeating the recursion. (I misspoke saying you make each call twice, one call is made once and the other is made twice.)

    if OJ is saying null doesn't exist, use NULL or nullptr. null is a Java keyword, NULL is a common but not universal c/c++ macro, and nullptr is a c++11 keyword.
    (If you use an old c++ compiler, it won't recognize nullptr, but might recognize NULL; before the c++11 update, best practice was to use 0, using the macro NULL which expands to 0 was common; longer ago, some compilers shipped with libraries that defined NULL to something other than 0, which caused problems, which motivated to best practice of using 0 and the addition of nullptr in c++11.)


Log in to reply
 

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