UVa # 112 트리 합계

Question

나는 UVa #112 Tree Summing에서 일하고있다. 나는 실용적인 해결책이라고 생각하지만 내 문제에 대한 기본적인 오해 때문에 온라인 판사가 인정하지 않습니다. 고려 다음 입력 :

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

또는 도식적으로이 나무의 모양 : 두 개 이상의 작업 솔루션에 따르면

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

, 위의 입력에 대한 올바른 출력은 다음과 같습니다

yes 
no 

그러나 두 번째 이유가 '아니오'여야하는 이유를 이해할 수 없습니다. 그것은 나무의 가장 오른쪽 경로가 적당한 합계를 내야하는 것처럼 나에게 보인다. 내가 뭘 놓치고 있니?

Answer 1

쉬운.

트리 :

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