A stupid macro caused to Time limited exceeded


  • 2
    M

    At first I used a macro to get the smaller of two number.

    //#define min(a,b)  a>b?b:a
    class Solution {
    public:
        int minDepth(TreeNode* root) {
            if(!root) return 0;
            if(root->left && root->right){
                auto min  = [](int a, int b){ return a>b?b:a; };
                return 1 + min(minDepth(root->left), minDepth(root->right));
            }else if(root->left){
                return 1 + minDepth(root->left);
            }else if(root->right){
                return 1 + minDepth(root->right);
            }
            return 1;
        }
    };
    

    Of course, I got a Time limit exceeded. I spent hours on finding the reason.

    In fact, the nodes were computed repeatedly due to the expansion of the macro.

    The farther the node is from the root, the more times it is computed.

    Maybe helpful for you guys. :)


  • 0
    L

    Thank you, it did help me a lot. I used the ternary operator with recursion and also caused to Time limited exceeded.


  • 0
    J

    Thank you so much for posting this.
    I got the same issue for this problem and the other one before.
    Your posting helped a lot !


Log in to reply
 

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