If you structure your data into a hash based tree then the following may help:

use strict;
use warnings;
use Data::Dump::Streamer;

my $branch1 = {
    Leaves => [qw(Leaf1 Leaf2)],
    Branch2 => {
        Leaves => [qw(Leaf3)],
        Branch3 => {
            Leaves => [qw(Leaf4 Leaf5)],
            Branch4 => {
                Leaves => [qw(Leaf6)],
                }
            }
        },
    Branch5 => {
        Leaves => [qw(Leaf7)],
        Branch6 => {
            Leaves => [qw(Leaf8 Leaf9)],
            }
        },  
    };

print "Original Tree:\n";
Dump ($branch1);
removeBranch ($branch1);
print "New Tree:\n";
Dump ($branch1);


sub removeBranch {
    my ($root, $branch) = @_;
    my $leafKey;
    my $keep;

    $branch = $root unless $branch;

    for my $child (keys %$branch) {
        if ('ARRAY' eq ref $branch->{$child}) {
            $leafKey = $child;
            next;
        }

        if (removeBranch ($root, $branch->{$child})) {
            delete $branch->{$child};
        } else {
            $keep = 1;
        }
    }

    return ! $keep unless $leafKey;
    
    my $leaves = $branch->{$leafKey};
    return undef if @$leaves > 1; # Leave this branch alone

    push @{$root->{Leaves}}, @$leaves;
    delete $branch->{$leafKey};
    return ! $keep;
}


__DATA__
Branch1 (Leaf1 Leaf2)
    Branch2 (Leaf3)
        Branch3 (Leaf4 Leaf5)
            Branch4 (Leaf6)
    Branch5 (Leaf7)
        Branch6 (Leaf8 Leaf9)
    
Branch1 (Leaf1 Leaf2 Leaf3 Leaf6 Leaf7)
    Branch3 (Leaf4 Leaf5)
[download]

Prints:

Original Tree:
$HASH1 = {
           Branch2 => {
                        Branch3 => {
                                     Branch4 => { Leaves => [ 'Leaf6' 
+] },
                                     Leaves  => [
                                                  'Leaf4',
                                                  'Leaf5'
                                                ]
                                   },
                        Leaves  => [ 'Leaf3' ]
                      },
           Branch5 => {
                        Branch6 => { Leaves => [
                                     'Leaf8',
                                     'Leaf9'
                                   ] },
                        Leaves  => [ 'Leaf7' ]
                      },
           Leaves  => [
                        'Leaf1',
                        'Leaf2'
                      ]
         };
New Tree:
$HASH1 = {
           Branch2 => { Branch3 => { Leaves => [
                        'Leaf4',
                        'Leaf5'
                      ] } },
           Branch5 => { Branch6 => { Leaves => [
                        'Leaf8',
                        'Leaf9'
                      ] } },
           Leaves  => [
                        'Leaf1',
                        'Leaf2',
                        'Leaf6',
                        'Leaf3',
                        'Leaf7'
                      ]
         };
[download]