diff options
| author | User Person <usermanperson+github@gmail.com> | 2020-04-19 14:29:04 -0400 |
|---|---|---|
| committer | User Person <usermanperson+github@gmail.com> | 2020-04-19 14:29:04 -0400 |
| commit | 92624b133a12b4b3e60daa51665815b866c27535 (patch) | |
| tree | 0f4609c96ff506525faa073b8c2cea1e1bec5ef7 /challenge-056/user-person/python/ch-2.py | |
| parent | 949adafd20491ac6dffc519478e341fc263459a0 (diff) | |
| download | perlweeklychallenge-club-92624b133a12b4b3e60daa51665815b866c27535.tar.gz perlweeklychallenge-club-92624b133a12b4b3e60daa51665815b866c27535.tar.bz2 perlweeklychallenge-club-92624b133a12b4b3e60daa51665815b866c27535.zip | |
User-person's solutions for challenge 56.
Diffstat (limited to 'challenge-056/user-person/python/ch-2.py')
| -rwxr-xr-x | challenge-056/user-person/python/ch-2.py | 75 |
1 files changed, 75 insertions, 0 deletions
diff --git a/challenge-056/user-person/python/ch-2.py b/challenge-056/user-person/python/ch-2.py new file mode 100755 index 0000000000..b33f174a8e --- /dev/null +++ b/challenge-056/user-person/python/ch-2.py @@ -0,0 +1,75 @@ +#!/usr/bin/env python3 + +########################################################################### +# script name: ch-2.py # +# # +# 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 # +# # +########################################################################### + +class Node: + def __init__(self,key): + self.left = None + self.right = None + self.val = key + +branchMemory = [] +k = 22 +match = 0 + +def preOrder(root, toLeafSum): + if root: + toLeafSum += root.val + if root.left != None and root.right != None: + branchMemory.append(toLeafSum) + if root.left == None and root.right == None: + if toLeafSum == k: + global match + match += 1 + if len(branchMemory) > 0: + toLeafSum = branchMemory.pop() + preOrder(root.left, toLeafSum) + preOrder(root.right, toLeafSum) + +bTree = Node(5) +bTree.left = Node(4) +bTree.left.left = Node(11) +bTree.left.left.left = Node(7) +bTree.left.left.right = Node(2) +bTree.right = Node(8) +bTree.right.left = Node(13) +bTree.right.right = Node(9) +bTree.right.right.right = Node(1) + +tLS = 0 +preOrder(bTree,tLS) + +if match == 0: + print('No branch equals', k) +elif match == 1: + print('1 branch equals', k) +else: + print(match, 'branches equal', k) |