BFS in C++


  • 0
    B

    Self explanatory. BFS should be faster than the recursive DFS as it exits as soon as it hits the first end node

        int minDepth(TreeNode* root) {
            if (!root) return 0;
            queue<TreeNode*> qeven, qodd;
            qeven.push(root);
            int level = 0;
            while (!qeven.empty() || !qodd.empty())
            {
                queue<TreeNode*>& qnow = (level%2 == 0) ? qeven : qodd;
                queue<TreeNode*>& qnxt = (level%2 == 0) ? qodd : qeven;            
                
                TreeNode* node = qnow.front(); qnow.pop();
                if (!node->left && !node->right) return level+1;
                if (qnow.empty()) level++;  //this queue emptied after the last pop
                
                if (node->left)  qnxt.push(node->left);
                if (node->right) qnxt.push(node->right);
            }
        }

Log in to reply
 

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