Recursive & Iterative solutions in CPP


  • 0
    B

    Here is two way of solving this problem, hope you like it:)
    Try to use one queue instead of two to implement an level order traversal.

    /*
      Recursive
     */
    class Solution {
    public:
        int minDepth(TreeNode* root) {
            if(! root){
                return 0;
            }
            if(root -> left == NULL){
                return minDepth(root -> right) + 1;
            }
            if(root -> right == NULL){
                return minDepth(root -> left) + 1;
            }
            return min(minDepth(root -> left), minDepth(root -> right)) + 1;
        }
    };
    
    /*
      Iterative
      Use only one queue to do the BFS, 
      use a NULL pointer(or whatever) to distinguish the last element of a    certain level
     */
    class Solution {
    public:
        int minDepth(TreeNode* root) {
            int min_depth = 1;
            if(root == NULL){
                return 0;
            }
            queue<TreeNode*> q;
            q.push(root);
            q.push(NULL);
            while(! q.empty()){
                TreeNode* cur = q.front();
                q.pop();
                if(cur == NULL){
                    q.push(NULL);
                    min_depth ++;
                }
                else{
                    if(cur -> left == NULL && cur -> right == NULL){
                        return min_depth;
                    }
                    if(cur -> left){
                        q.push(cur -> left);
                    }
                    if(cur -> right){
                        q.push(cur -> right);
                    }
                }
            }   
            return min_depth;
        }
    };

Log in to reply
 

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