UVa 112

From Algorithmist
Jump to navigation Jump to search

112 - Tree Summing[edit]

Summary[edit]

Given a binary tree, determine if it is possible to traverse the tree to obtain a specific sum.

Explanation[edit]

Gotchas[edit]

  • The input data could have negative values (the label in the nodes and also the integer to be found).
  • As the description says, there could be empty trees.
  • The path must end in a leaf node (of the form (integer () ()), not in a ().

Notes[edit]

Implementations[edit]

It's easy to implement the tree (implicitly) if you think of parenthesis as a stack.

The input data is the result of a depth first search of the tree.

Optimizations[edit]

Input[edit]

22 (5(4(11(7()())(2()()))()) (8(13()())(4()(1()()))))
20 (5(4(11(7()())(2()()))()) (8(13()())(4()(1()()))))
10 (3 
     (2 (4 () () )
        (8 () () ) )
     (1 (6 () () )
        (4 () () ) ) )
5 ()
0 ()
5 (5 () ())
5 ( 5 () () )
5 (1 (3 () ()) (4 () ()))
5 (18 ( -13 ( ) (  ))())
0 (1 ()(-2 () (1()()) ) )
2 (1 () (1 () (1 () () ) ) )
10 (5 () (5 () (5 () (5 () (4 () () ) ) ) ) )
10 (5 () (5 () (5 () (5 ( 3 () () ) (4 () () ) ) ) ) )
20 (5 () (5 () (5 () (5 () (4 () () ) ) ) ) )

Output[edit]

yes
no
yes
no
no
yes
yes
yes
yes
yes
no
no
no
no

Solutions[edit]

References[edit]

  1. Reference 1

Categories here, use the form [[Category:UVa Online Judge|112]] [[Category: Category Name]], see Categories for a list