C++ dfs and bfs solutions.


  • 6
    C
    // DFS
    int minDepth(TreeNode* root) {
        if (!root)  
            return 0;
        if (root->left && root->right)  
            return min(minDepth(root->left), minDepth(root->right))+1;
        return max(minDepth(root->left), minDepth(root->right))+1;
    }
    
    // BFS
    int minDepth1(TreeNode *root) {
        int res = 0;
        queue<TreeNode *> myQueue;
        if (root)
            myQueue.push(root);
        while (!myQueue.empty()) {
            int l = myQueue.size();
            res++;
            for (int i = 0; i < l; i++) {
                TreeNode *tmp = myQueue.front();
                if (!(tmp->left) && !(tmp->right))
                    return res;
                if (tmp->left)
                    myQueue.push(tmp->left);
                if (tmp->right)
                    myQueue.push(tmp->right);
                myQueue.pop();
            }
        }
        return res;
    }

  • 1
    B

    Could you perhaps explain why you

    return max(minDepth(root->left), minDepth(root->right))+1;
    

    in the 6th line. Not quite sure why that works.


  • 0
    Z

    If root->left == NULL, and root->right != NULL,we should get the depth of root->right.
    If root->right == NULL, root->left != NULL, we should get the depth of root->left.


Log in to reply
 

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