Here's a way that 'schedules' a dir for removal later only when a file was removed within it.

#! /usr/bin/perl -w

use strict;
use File::Find;


my @dirs;

# Process each file that was found
sub wanted {
    # Use your criteria here for what to delete
    if (/foo/) {
        # Delete the file
        unlink $_;

        # Save the dir for later
        push @dirs, $File::Find::dir;
    }
}

# Replace . with your starting dir
find \&wanted, '.';

# Now try to remove the dirs, rmdir will fail if the dir isn't empty
rmdir $_ foreach reverse @dirs;
[download]

Update: oops, just read above node about removing dirs with other dirs inside them. Modified the script to not use the hash for dir path storage, but instead use the reverse list.