BFS, C++, 8ms, Beats 99.94% submissions


  • 32
    int minDepth(TreeNode* root) {
        if (root == NULL) return 0;
        queue<TreeNode*> Q;
        Q.push(root);
        int i = 0;
        while (!Q.empty()) {
            i++;
            int k = Q.size();
            for (int j=0; j<k; j++) {
                TreeNode* rt = Q.front();
                if (rt->left) Q.push(rt->left);
                if (rt->right) Q.push(rt->right);
                Q.pop();
                if (rt->left==NULL && rt->right==NULL) return i;
            }
        }
        return -1; //For the compiler thing. The code never runs here.
    }

  • 6
    Z

    why not use

    if (rt->left==NULL && rt->right==NULL){return i;}
    

    replace

    if (rt->left==NULL && rt->right==NULL){flag=true;break;}

  • 0

    Thank you so much, bro! Saved me a bunch of lines. I didn't know why I did that stupid.


  • 0
    O

    The next-to-last line "return i;" is unnecessary.


  • 0

    Exactly! Thank you! :x


  • 0
    A

    Good solution!But why i try the code and costs 12ms and you costs 8ms?Thx.


  • 0

    After delete the "return i", it will have compile error. you may need to return a int at the end.
    Have you tried the code again?


  • 0

    Yeah, they just changed how it is compiled. I just updated the code. Thanks.


  • 0
    A

    I have a question about the performance. why from my side, your code only beat around 30% submissions, even worse than dfs?

    I think theoretically your way should be better than the dfs. Anybody can give me a clue?


Log in to reply
 

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