My C++ recursive solution with comment


  • 1
    V
    class Solution {
    public:
        int minDepth(TreeNode* root) {
            int l = 0, r = 0; //l denotes the depth of left subtree,r denotes ...right subtree
            
            if (root == NULL) return 0;
            if (root->left == NULL && root->right == NULL) //the current node is leaf
                return 1;
            if (root->left != NULL && root->right != NULL) //the current node has two subtrees
            {
                l = minDepth(root->left);
                r = minDepth(root->right);
            }
            else if (root->left != NULL)
                l = minDepth(root->left);
            else if (root->right != NULL)
                r = minDepth(root->right);
                
            if (l != 0 && r == 0) //the current node is not the leaf,it just has left subtree,return 'depth of left tree + 1'
                return l+1;
            else if (l == 0 && r != 0) //the current node is not the leaf,it just has right subtree,return 'depth of right subtree + 1'
                return r+1;
            else
                return (l > r) ? r+1 : l+1; //the current node has two subtrees, return the smaller depth of the both
        }
    };

Log in to reply
 

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