My BFS solution(C++)


  • 3
    Z
     class Solution {
        public:        
            int minDepth(TreeNode *root) {            
                queue<pair<TreeNode *,int>> nodes;            
                int depth = 0;
                if(root == NULL){
                    return 0;
                }
                nodes.push(pair<TreeNode*,int>(root,1));
                while(!nodes.empty()){
                    pair<TreeNode*,int> next = nodes.front();
                    nodes.pop();
                    if(next.first->left==NULL && next.first->right==NULL){
                        depth = next.second;
                        break;
                    }
                    if(next.first->left!=NULL){
                        nodes.push(pair<TreeNode*,int>(next.first->left, next.second+1));
                    }
                    if(next.first->right!=NULL){
                        nodes.push(pair<TreeNode*,int>(next.first->right, next.second+1));
                    }
                }
                return depth;
            }
        };
    

    I use a FIFO queue to realize the BFS method and the int is used for storing the current depth. This problem is not suitable for DFS or recursion, which may waste much time.


  • 0
    U

    I also trie BSF, I was wondering BSF would be more efficient than recursion because of function calls stack, but it turned out BSF costs more time, do you know why?


Log in to reply
 

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