tree - UVa #112 树求和

Question

我正在研究 UVa #112 Tree Summing .我有我认为应该可行的解决方案，但由于我对问题的基本误解，它没有被在线法官接受。考虑以下输入:

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

或者在图表上，树看起来像:

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

根据至少两个可行的解决方案，上述输入的正确输出是:

yes
no

但是，我不明白为什么第二个应该是“否”。在我看来，树最右边的路径应该给出正确的总和。我错过了什么？

Answer 1

简单。

树:

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

叶子是这种形式:(integer () ())

因此树只有一片叶子:(1 () ())

这个叶子节点的总和是 78。78 不是 77。结果:否。

你认为最右的路径，根据定义是没有的。

第一棵树:

(-1()())

它只是一个单叶节点。一条路。总和为-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)