challenge-056/user-person/perl/ch-2.pl


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

#!/usr/bin/env perl

###########################################################################
# script name: ch-2.pl                                                    #
#                                                                         #
# https://github.com/user-person                                          #
#                                                                         #
# https://perlweeklychallenge.org/blog/perl-weekly-challenge-056/         #
#                                                                         #
# Path Sum                                                                #
# You are given a binary tree and a sum, write a script to find if        #
# the tree has a path such that adding up all the values along the path   #
# equals the given sum. Only complete paths (from root to leaf node) may  #
# be considered for a sum.                                                #
#                                                                         #
# Example                                                                 #
# Given the below binary tree and sum = 22,                               #
#                                                                         #
#             5                                                           #
#            / \                                                          #
#           4   8                                                         #
#          /   / \                                                        #
#         11  13  9                                                       #
#        /  \      \                                                      #
#       7    2      1                                                     #
#                                                                         #
# For the given binary tree, the partial path sum 5 -> 8 -> 9 = 22 is     #
# not valid.                                                              #
# The script should return the path 5 -> 4 -> 11 -> 7 whose sum is 22     #
#                                                                         #
###########################################################################

use strict;
use warnings;

use Tree::Binary;

my($btree) = Tree::Binary -> new('5')
    -> setLeft(
        Tree::Binary -> new('4')
              -> setLeft (
                  Tree::Binary -> new('11')
                        -> setLeft (Tree::Binary -> new('7'))
                        -> setRight(Tree::Binary -> new('2'))
                  )
    )
    -> setRight (
        Tree::Binary -> new('8')
              -> setLeft (Tree::Binary -> new('13'))
              -> setRight (
                      Tree::Binary -> new('9')
                            -> setRight (
                                Tree::Binary -> new('1'))
                 )
             );

my @branchMemory = ();
my $k = 22;
my $match = 0;
my $toLeafSum = 0;

$btree -> traverse
    (
        sub
            {
                my($tree) = @_;
                $toLeafSum += $tree -> getNodeValue;

                if ( $tree -> hasLeft and $tree -> hasRight ) {
                    push @branchMemory, $toLeafSum;
                }

                if ( $tree->isLeaf) {
                    ++$match if $toLeafSum == $k;
                    $toLeafSum = pop @branchMemory;
                }
          });

if ($match == 0 ) {
    print "No branch equals $k\n";
} elsif ($match == 1) {
    print "1 branch equals $k\n";
} else {
    print "$match branches equal $k\n";
}

__END__
output:

1 branch equals 22