UVa # 112 Summation Tree

Question

I am working on UVa # 112 Tree Summing . I have something that, in my opinion, should be a working solution, but it is not accepted by the online judge due to a basic misunderstanding of the problem on my part. Consider the following inputs:

-1 (-1()())
77 (77(1()())())

or schematically, the trees look like this:

  -1              77
 /   \           /  \
()    ()        1    ()
               / \
              ()  ()

According to at least two working solutions, the correct conclusion is for the above inputs:

yes
no

However, I do not understand why the second should be "no." It seems to me that the rightmost path of the tree should give the correct amount. What am I missing?

Answer 1

Easy.

Wood:

(77(1()())())

The sheet has the following form: (integer () ())

Thus, the tree has only one leaf: (1 () ())

78. 78 77. : .

, , .

:

(-1()())

node. . -1. -1 = -1. : .

Lisp:

(defun leaf-p (node)
  "is the node a leaf?"
  (and (= (length node) 3)
       (integerp (first node))
       (null (second node))
       (null (third node))))

(defun path-sums (tree)
  "returns a list of all sums for each path"
  (if (leaf-p tree)
      (list (first tree))
    (mapcar (lambda (s)
              (+ (first tree) s))
            (append (when (second tree)
                      (path-sums (second tree)))
                    (when (third tree)
                      (path-sums (third tree)))))))

(defun tree-sum-p (sum tree)
  (member sum (path-sums tree)))

CL-USER 223 > (path-sums '(-1()()))
(-1)

CL-USER 224 > (path-sums '(77(1()())()))
(78)