BFS in C++

  • 0

    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;
            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.