UVa # 112 Tree Summing - PullRequest
Новая
       7

UVa # 112 Tree Summing

3 голосов
/ 13 марта 2010

Я работаю над суммированием деревьев UVa # 112 . У меня есть то, что я думаю, должно быть рабочим решением, но оно не принимается онлайн-судьей из-за базового недопонимания проблемы с моей стороны. Рассмотрим следующие входные данные: 

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

или схематически деревья выглядят так: 

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

Согласно, по крайней мере, двум рабочим решениям, правильный выход для указанных выше входных данных: 

yes
no

Однако я не понимаю, почему второе должно быть «нет». Мне кажется, что самый правый путь дерева должен дать правильную сумму. Чего мне не хватает?

1 Ответ

3 голосов
/ 13 марта 2010

Легко.

Дерево: 

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

Лист имеет следующую форму: (целое число () ())

Таким образом, у дерева есть только один лист: (1 () ())

Сумма узлов этого листа равна 78. 78 - не 77. Результат: нет .

То, что вы считаете самым правым путем, не соответствует определению.

Первое дерево: 

(-1()())

Это просто один листовой узел. Один путь. Сумма -1. -1 = -1 Результат: да .

Мы можем проверить это с помощью программы на Лиспе: 

(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)
...